<!DOCTYPE html>
<html lang="en-US">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>开发岗-冷门考点 | whoway</title>
    <meta name="description" content="Personal Blog Website">
    <link rel="icon" href="/images/photo.jpg">
  <link rel="manifest" href="/images/photo.jpg">
  <link rel="apple-touch-icon" href="/images/photo.jpg">
  <meta http-quiv="pragma" cotent="no-cache">
  <meta http-quiv="pragma" cotent="no-cache,must-revalidate">
  <meta http-quiv="expires" cotent="0">
    
    <link rel="preload" href="/assets/css/0.styles.0dbae9ec.css" as="style"><link rel="preload" href="/assets/js/app.c70e21ad.js" as="script"><link rel="preload" href="/assets/js/55.d8f9004b.js" as="script"><link rel="prefetch" href="/assets/js/10.15222a53.js"><link rel="prefetch" href="/assets/js/100.7e0e5a86.js"><link rel="prefetch" href="/assets/js/101.efd59f25.js"><link rel="prefetch" href="/assets/js/102.dfbdc06c.js"><link rel="prefetch" href="/assets/js/103.d3ab2109.js"><link rel="prefetch" href="/assets/js/104.117957ef.js"><link rel="prefetch" href="/assets/js/105.046e8ff3.js"><link rel="prefetch" href="/assets/js/106.aebdc17d.js"><link rel="prefetch" href="/assets/js/107.248733c2.js"><link rel="prefetch" href="/assets/js/108.a2fecadc.js"><link rel="prefetch" href="/assets/js/109.35196857.js"><link rel="prefetch" href="/assets/js/11.770642f2.js"><link rel="prefetch" href="/assets/js/110.cf3d973c.js"><link rel="prefetch" href="/assets/js/111.f985889a.js"><link rel="prefetch" href="/assets/js/112.ad614f41.js"><link rel="prefetch" href="/assets/js/113.f666653c.js"><link rel="prefetch" href="/assets/js/114.c6c3f384.js"><link rel="prefetch" href="/assets/js/115.e51d3c2f.js"><link rel="prefetch" href="/assets/js/116.4f4b39f5.js"><link rel="prefetch" href="/assets/js/117.99352e11.js"><link rel="prefetch" href="/assets/js/118.c6ae6572.js"><link rel="prefetch" href="/assets/js/119.4ccbe778.js"><link rel="prefetch" href="/assets/js/12.042a92ff.js"><link rel="prefetch" href="/assets/js/120.edda1c4f.js"><link rel="prefetch" href="/assets/js/121.30a638ed.js"><link rel="prefetch" href="/assets/js/122.6efcefb1.js"><link rel="prefetch" href="/assets/js/123.91e6665b.js"><link rel="prefetch" href="/assets/js/124.f27e3d7e.js"><link rel="prefetch" href="/assets/js/125.c75712d5.js"><link rel="prefetch" href="/assets/js/126.ed756cce.js"><link rel="prefetch" href="/assets/js/127.2f06c74c.js"><link rel="prefetch" href="/assets/js/128.d5f6f30e.js"><link rel="prefetch" href="/assets/js/129.508b7eed.js"><link rel="prefetch" href="/assets/js/13.b5280c37.js"><link rel="prefetch" href="/assets/js/130.dc05f9aa.js"><link rel="prefetch" href="/assets/js/131.e0ba69b1.js"><link rel="prefetch" href="/assets/js/132.d79bcaa4.js"><link rel="prefetch" href="/assets/js/133.34acc01a.js"><link rel="prefetch" href="/assets/js/134.dabf64d5.js"><link rel="prefetch" href="/assets/js/135.ad90c915.js"><link rel="prefetch" href="/assets/js/136.dbb0074f.js"><link rel="prefetch" href="/assets/js/137.284ad365.js"><link rel="prefetch" href="/assets/js/138.a4b6856f.js"><link rel="prefetch" href="/assets/js/139.c9c1e20f.js"><link rel="prefetch" href="/assets/js/14.df02ba38.js"><link rel="prefetch" href="/assets/js/140.8b0a9269.js"><link rel="prefetch" href="/assets/js/141.9c7759c5.js"><link rel="prefetch" href="/assets/js/142.a4201a82.js"><link rel="prefetch" href="/assets/js/143.d7da6e8c.js"><link rel="prefetch" href="/assets/js/144.5e48e65d.js"><link rel="prefetch" href="/assets/js/145.a0e2633c.js"><link rel="prefetch" href="/assets/js/146.3c775f9b.js"><link rel="prefetch" href="/assets/js/147.22add89a.js"><link rel="prefetch" href="/assets/js/148.cfde1009.js"><link rel="prefetch" href="/assets/js/149.ffc835b5.js"><link rel="prefetch" href="/assets/js/15.fbdfc4ee.js"><link rel="prefetch" href="/assets/js/150.406c4b20.js"><link rel="prefetch" href="/assets/js/151.b2040eea.js"><link rel="prefetch" href="/assets/js/152.7bc65661.js"><link rel="prefetch" href="/assets/js/153.1d7c65e3.js"><link rel="prefetch" href="/assets/js/154.1309de49.js"><link rel="prefetch" href="/assets/js/155.81d3ee1f.js"><link rel="prefetch" href="/assets/js/156.154a4ef2.js"><link rel="prefetch" href="/assets/js/16.e5eb6147.js"><link rel="prefetch" href="/assets/js/17.57853c4a.js"><link rel="prefetch" href="/assets/js/18.cb9d7518.js"><link rel="prefetch" href="/assets/js/19.f354dc47.js"><link rel="prefetch" href="/assets/js/2.570d8a23.js"><link rel="prefetch" href="/assets/js/20.b5af7fad.js"><link rel="prefetch" href="/assets/js/21.0b1928fe.js"><link rel="prefetch" href="/assets/js/22.f78666de.js"><link rel="prefetch" href="/assets/js/23.29c3f366.js"><link rel="prefetch" href="/assets/js/24.6f596516.js"><link rel="prefetch" href="/assets/js/25.14067b60.js"><link rel="prefetch" href="/assets/js/26.74ba4989.js"><link rel="prefetch" href="/assets/js/27.13d60edd.js"><link rel="prefetch" href="/assets/js/28.9523cb32.js"><link rel="prefetch" href="/assets/js/29.8ec842e9.js"><link rel="prefetch" href="/assets/js/3.3fb3d2e0.js"><link rel="prefetch" href="/assets/js/30.805597a8.js"><link rel="prefetch" href="/assets/js/31.831b195d.js"><link rel="prefetch" href="/assets/js/32.063c672d.js"><link rel="prefetch" href="/assets/js/33.6d93fac3.js"><link rel="prefetch" href="/assets/js/34.56e8263c.js"><link rel="prefetch" href="/assets/js/35.dbe688bb.js"><link rel="prefetch" href="/assets/js/36.dc5af2c1.js"><link rel="prefetch" href="/assets/js/37.0a7494f6.js"><link rel="prefetch" href="/assets/js/38.fe4fc171.js"><link rel="prefetch" href="/assets/js/39.f5ed5e92.js"><link rel="prefetch" href="/assets/js/4.2c405ec8.js"><link rel="prefetch" href="/assets/js/40.fe7e2714.js"><link rel="prefetch" href="/assets/js/41.30b0811d.js"><link rel="prefetch" href="/assets/js/42.76f52d62.js"><link rel="prefetch" href="/assets/js/43.e7bb0817.js"><link rel="prefetch" href="/assets/js/44.ead0e883.js"><link rel="prefetch" href="/assets/js/45.235df046.js"><link rel="prefetch" href="/assets/js/46.5f09e829.js"><link rel="prefetch" href="/assets/js/47.67116354.js"><link rel="prefetch" href="/assets/js/48.31f34543.js"><link rel="prefetch" href="/assets/js/49.10b5ebba.js"><link rel="prefetch" href="/assets/js/5.6f47322c.js"><link rel="prefetch" href="/assets/js/50.c0f0b7f1.js"><link rel="prefetch" href="/assets/js/51.5143f3bf.js"><link rel="prefetch" href="/assets/js/52.eeddfd48.js"><link rel="prefetch" href="/assets/js/53.eb790db5.js"><link rel="prefetch" href="/assets/js/54.8fe5421c.js"><link rel="prefetch" href="/assets/js/56.62ac9b92.js"><link rel="prefetch" href="/assets/js/57.a9caec0d.js"><link rel="prefetch" href="/assets/js/58.f93fc522.js"><link rel="prefetch" href="/assets/js/59.a81a03aa.js"><link rel="prefetch" href="/assets/js/6.8c2ea393.js"><link rel="prefetch" href="/assets/js/60.ab782775.js"><link rel="prefetch" href="/assets/js/61.6dd12daf.js"><link rel="prefetch" href="/assets/js/62.76f4b01f.js"><link rel="prefetch" href="/assets/js/63.6f8a4742.js"><link rel="prefetch" href="/assets/js/64.6f8bb1fa.js"><link rel="prefetch" href="/assets/js/65.4120a44b.js"><link rel="prefetch" href="/assets/js/66.360c2d2b.js"><link rel="prefetch" href="/assets/js/67.26f84d32.js"><link rel="prefetch" href="/assets/js/68.68f45e5e.js"><link rel="prefetch" href="/assets/js/69.e311eb56.js"><link rel="prefetch" href="/assets/js/7.6762b2d7.js"><link rel="prefetch" href="/assets/js/70.cea82674.js"><link rel="prefetch" href="/assets/js/71.783ddcf7.js"><link rel="prefetch" href="/assets/js/72.e5467385.js"><link rel="prefetch" href="/assets/js/73.b8fb681b.js"><link rel="prefetch" href="/assets/js/74.1bae37db.js"><link rel="prefetch" href="/assets/js/75.024387e5.js"><link rel="prefetch" href="/assets/js/76.a8e53010.js"><link rel="prefetch" href="/assets/js/77.8c55500a.js"><link rel="prefetch" href="/assets/js/78.7ce90bf5.js"><link rel="prefetch" href="/assets/js/79.ef71713f.js"><link rel="prefetch" href="/assets/js/8.788a6364.js"><link rel="prefetch" href="/assets/js/80.acad589d.js"><link rel="prefetch" href="/assets/js/81.02670d10.js"><link rel="prefetch" href="/assets/js/82.53b7b1ac.js"><link rel="prefetch" href="/assets/js/83.99eb8581.js"><link rel="prefetch" href="/assets/js/84.d1535ce3.js"><link rel="prefetch" href="/assets/js/85.fe2b7de9.js"><link rel="prefetch" href="/assets/js/86.41850272.js"><link rel="prefetch" href="/assets/js/87.1cdc6df9.js"><link rel="prefetch" href="/assets/js/88.01bf3461.js"><link rel="prefetch" href="/assets/js/89.17c69819.js"><link rel="prefetch" href="/assets/js/9.3813842d.js"><link rel="prefetch" href="/assets/js/90.f6ae7e35.js"><link rel="prefetch" href="/assets/js/91.507bc284.js"><link rel="prefetch" href="/assets/js/92.90551782.js"><link rel="prefetch" href="/assets/js/93.dc442d78.js"><link rel="prefetch" href="/assets/js/94.315f4e94.js"><link rel="prefetch" href="/assets/js/95.ccd6c6bf.js"><link rel="prefetch" href="/assets/js/96.0c6d89d0.js"><link rel="prefetch" href="/assets/js/97.1a9f10a9.js"><link rel="prefetch" href="/assets/js/98.43be3caa.js"><link rel="prefetch" href="/assets/js/99.54c8207b.js">
    <link rel="stylesheet" href="/assets/css/0.styles.0dbae9ec.css">
  </head>
  <body>
    <div id="app" data-server-rendered="true"><div class="theme-container"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><!----> <span class="site-name">whoway</span></a> <div class="links" style="max-width:nullpx;"><div class="search-box"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">🎓Coding</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/00.Coding/TheBeautyOfProgramming/" class="nav-link">🔖编程之美题解</a></li><li class="dropdown-item"><!----> <a href="/00.Coding/CodeWarehouse/" class="nav-link">🔖代码意识流</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">🚀语言</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/01.Language/Overview/" class="nav-link">🔖概述</a></li><li class="dropdown-item"><!----> <a href="/01.Language/C/" class="nav-link">⭐️C</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Cpp/" class="nav-link">🚀C++</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Java/" class="nav-link">☕️Java</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Python/" class="nav-link">🧩Python3</a></li></ul></div></div><div class="nav-item"><a href="/02.Hardware/" class="nav-link">✔️硬件基础</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">⭐️软件基础</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/03.Software/01.DataStructureAndAlgorithm/" class="nav-link router-link-active">🐾数据结构和算法</a></li><li class="dropdown-item"><!----> <a href="/03.Software/02.OS/" class="nav-link">💻操作系统</a></li><li class="dropdown-item"><!----> <a href="/03.Software/03.Net/" class="nav-link">☁️计算机网络</a></li><li class="dropdown-item"><!----> <a href="/03.Software/04.SE/" class="nav-link">✅软件工程</a></li></ul></div></div><div class="nav-item"><a href="/04.Database/" class="nav-link">🎨数据库</a></div><div class="nav-item"><a href="/05.Engineer/" class="nav-link">🔖学术/工程</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">⚙️工具</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/06.Tools/01.employment/" class="nav-link">🔖求职</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/02.efficiency/" class="nav-link">🚀效能</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/03.windows/" class="nav-link">⚙️Windows</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/04.design/" class="nav-link">🧩设计</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/05.linux/" class="nav-link">🐉Linux</a></li></ul></div></div><div class="nav-item"><a href="https://github.com/whoway" target="_blank" rel="noopener noreferrer" class="nav-link external">
  GitHub
  <svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></div> <!----></nav></div></header> <div class="sidebar-mask"></div> <div class="sidebar"><nav class="nav-links"><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">🎓Coding</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/00.Coding/TheBeautyOfProgramming/" class="nav-link">🔖编程之美题解</a></li><li class="dropdown-item"><!----> <a href="/00.Coding/CodeWarehouse/" class="nav-link">🔖代码意识流</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">🚀语言</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/01.Language/Overview/" class="nav-link">🔖概述</a></li><li class="dropdown-item"><!----> <a href="/01.Language/C/" class="nav-link">⭐️C</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Cpp/" class="nav-link">🚀C++</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Java/" class="nav-link">☕️Java</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Python/" class="nav-link">🧩Python3</a></li></ul></div></div><div class="nav-item"><a href="/02.Hardware/" class="nav-link">✔️硬件基础</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">⭐️软件基础</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/03.Software/01.DataStructureAndAlgorithm/" class="nav-link router-link-active">🐾数据结构和算法</a></li><li class="dropdown-item"><!----> <a href="/03.Software/02.OS/" class="nav-link">💻操作系统</a></li><li class="dropdown-item"><!----> <a href="/03.Software/03.Net/" class="nav-link">☁️计算机网络</a></li><li class="dropdown-item"><!----> <a href="/03.Software/04.SE/" class="nav-link">✅软件工程</a></li></ul></div></div><div class="nav-item"><a href="/04.Database/" class="nav-link">🎨数据库</a></div><div class="nav-item"><a href="/05.Engineer/" class="nav-link">🔖学术/工程</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">⚙️工具</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/06.Tools/01.employment/" class="nav-link">🔖求职</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/02.efficiency/" class="nav-link">🚀效能</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/03.windows/" class="nav-link">⚙️Windows</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/04.design/" class="nav-link">🧩设计</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/05.linux/" class="nav-link">🐉Linux</a></li></ul></div></div><div class="nav-item"><a href="https://github.com/whoway" target="_blank" rel="noopener noreferrer" class="nav-link external">
  GitHub
  <svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></div> <!----></nav>  <ul class="sidebar-links"><li><div class="sidebar-group first"><p class="sidebar-heading open"><span>开发岗-冷门考点</span> <!----></p> <ul class="sidebar-group-items"><li><a href="/03.Software/01.DataStructureAndAlgorithm/Others/Part01.%E5%85%B6%E4%BB%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E6%A8%A1%E6%9D%BF.html#目录" class="sidebar-link">目录</a><ul class="sidebar-sub-headers"></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/Others/Part01.%E5%85%B6%E4%BB%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E6%A8%A1%E6%9D%BF.html#_01-树状数组（binary-indexed-tree）⭐️" class="sidebar-link">01.树状数组（Binary Indexed Tree）⭐️</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/Others/Part01.%E5%85%B6%E4%BB%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E6%A8%A1%E6%9D%BF.html#_1-1-引入问题" class="sidebar-link">1.1.引入问题</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/Others/Part01.%E5%85%B6%E4%BB%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E6%A8%A1%E6%9D%BF.html#_1-2-前置知识-lowbit-操作" class="sidebar-link">1.2.前置知识- lowbit()操作</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/Others/Part01.%E5%85%B6%E4%BB%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E6%A8%A1%E6%9D%BF.html#_1-3-树状数组–思想及实现" class="sidebar-link">1.3.树状数组–思想及实现</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/Others/Part01.%E5%85%B6%E4%BB%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E6%A8%A1%E6%9D%BF.html#_1-4-树状数组的扩展应用" class="sidebar-link">1.4.树状数组的扩展应用</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/Others/Part01.%E5%85%B6%E4%BB%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E6%A8%A1%E6%9D%BF.html#_1-5-总结与代码" class="sidebar-link">1.5.总结与代码</a></li></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/Others/Part01.%E5%85%B6%E4%BB%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E6%A8%A1%E6%9D%BF.html#_02-线段树⭐️" class="sidebar-link">02.线段树⭐️</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/Others/Part01.%E5%85%B6%E4%BB%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E6%A8%A1%E6%9D%BF.html#_2-1-线段树的基本概念" class="sidebar-link">2.1.线段树的基本概念</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/Others/Part01.%E5%85%B6%E4%BB%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E6%A8%A1%E6%9D%BF.html#_2-2-一维线段树" class="sidebar-link">2.2.一维线段树</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/Others/Part01.%E5%85%B6%E4%BB%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E6%A8%A1%E6%9D%BF.html#_2-3-二维线段树" class="sidebar-link">2.3.二维线段树</a></li></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/Others/Part01.%E5%85%B6%E4%BB%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E6%A8%A1%E6%9D%BF.html#_03-主席树⭐️" class="sidebar-link">03.主席树⭐️</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/Others/Part01.%E5%85%B6%E4%BB%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E6%A8%A1%E6%9D%BF.html#_3-1-主席树基础" class="sidebar-link">3.1.主席树基础</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/Others/Part01.%E5%85%B6%E4%BB%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E6%A8%A1%E6%9D%BF.html#（1）主席树基础" class="sidebar-link">（1）主席树基础</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/Others/Part01.%E5%85%B6%E4%BB%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E6%A8%A1%E6%9D%BF.html#（2）为什么叫“主席树”呢？" class="sidebar-link">（2）为什么叫“主席树”呢？</a></li></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/Others/Part01.%E5%85%B6%E4%BB%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E6%A8%A1%E6%9D%BF.html#_04-设计跳表⭐" class="sidebar-link">04.设计跳表⭐</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/Others/Part01.%E5%85%B6%E4%BB%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E6%A8%A1%E6%9D%BF.html#_4-1-跳表" class="sidebar-link">4.1.跳表</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/Others/Part01.%E5%85%B6%E4%BB%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E6%A8%A1%E6%9D%BF.html#_4-2-添加节点" class="sidebar-link">4.2.添加节点</a></li></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/Others/Part01.%E5%85%B6%E4%BB%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E6%A8%A1%E6%9D%BF.html#_05-trie-前缀树✅" class="sidebar-link">05.Trie-前缀树✅</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/Others/Part01.%E5%85%B6%E4%BB%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E6%A8%A1%E6%9D%BF.html#_5-1-字典树类代码" class="sidebar-link">5.1.字典树类代码</a></li></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/Others/Part01.%E5%85%B6%E4%BB%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E6%A8%A1%E6%9D%BF.html#_06-lru题解的衍生思考✅" class="sidebar-link">06.LRU题解的衍生思考✅</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/Others/Part01.%E5%85%B6%E4%BB%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E6%A8%A1%E6%9D%BF.html#_6-1-文章意义" class="sidebar-link">6.1.文章意义</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/Others/Part01.%E5%85%B6%E4%BB%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E6%A8%A1%E6%9D%BF.html#_6-2-ac代码" class="sidebar-link">6.2.AC代码</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/Others/Part01.%E5%85%B6%E4%BB%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E6%A8%A1%E6%9D%BF.html#_6-3-原始尝试代码（也ac了）" class="sidebar-link">6.3.原始尝试代码（也AC了）</a></li></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/Others/Part01.%E5%85%B6%E4%BB%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E6%A8%A1%E6%9D%BF.html#_07-字符串匹配算法⭐" class="sidebar-link">07.字符串匹配算法⭐</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/Others/Part01.%E5%85%B6%E4%BB%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E6%A8%A1%E6%9D%BF.html#_7-1-bf算法『暴力』" class="sidebar-link">7.1.BF算法『暴力』</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/Others/Part01.%E5%85%B6%E4%BB%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E6%A8%A1%E6%9D%BF.html#_7-2-rk算法" class="sidebar-link">7.2.RK算法</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/Others/Part01.%E5%85%B6%E4%BB%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E6%A8%A1%E6%9D%BF.html#_7-3-bm算法" class="sidebar-link">7.3.BM算法</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/Others/Part01.%E5%85%B6%E4%BB%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E6%A8%A1%E6%9D%BF.html#_1、坏字符规则" class="sidebar-link">1、坏字符规则</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/Others/Part01.%E5%85%B6%E4%BB%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E6%A8%A1%E6%9D%BF.html#_2、好后缀规则" class="sidebar-link">2、好后缀规则</a></li></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/Others/Part01.%E5%85%B6%E4%BB%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%E6%A8%A1%E6%9D%BF.html#参考资料" class="sidebar-link">参考资料</a><ul class="sidebar-sub-headers"></ul></li></ul></div></li></ul> </div> <div class="page"> <div class="content"><h1 id="开发岗-冷门考点"><a href="#开发岗-冷门考点" class="header-anchor">#</a> 开发岗-冷门考点</h1> <ul><li>00.Trie树</li> <li>01.树状数组</li> <li>02.线段树</li> <li>03.主席树</li> <li>04.差分数组——<a href="https://blog.csdn.net/qq_44786250/article/details/100056975" target="_blank" rel="noopener noreferrer">参考<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li> <li>05.字符串匹配</li></ul> <h2 id="目录"><a href="#目录" class="header-anchor">#</a> 目录</h2> <p>[TOC]</p> <h2 id="_01-树状数组（binary-indexed-tree）⭐️"><a href="#_01-树状数组（binary-indexed-tree）⭐️" class="header-anchor">#</a> 01.树状数组（Binary Indexed Tree）⭐️</h2> <ul><li>参考：<a href="https://www.bilibili.com/video/BV1pE41197Qj" target="_blank" rel="noopener noreferrer">B站传送门<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li></ul> <h3 id="_1-1-引入问题"><a href="#_1-1-引入问题" class="header-anchor">#</a> 1.1.引入问题</h3> <p>引入问题</p> <ul><li>给出一个长度为n的数组,完成以下两种操作
●将第x个数加上k
●输出区间[x,y]内每个数的和
题目来源: Luogu P3374树状数组1
给出一个数组要求支持<strong>单点修改</strong>和<strong>区间和的查询</strong>操作</li></ul> <h4 id="_1、对比两种情况"><a href="#_1、对比两种情况" class="header-anchor">#</a> 1、对比两种情况</h4> <table><thead><tr><th></th> <th></th> <th></th></tr></thead> <tbody><tr><td></td> <td>暴力算法</td> <td>引入DS-树状数组</td></tr> <tr><td>单点修改</td> <td>$O(1)$</td> <td>$O(logn)$</td></tr> <tr><td>区间和查询</td> <td>$O(n)$</td> <td>$O(logn)$</td></tr> <tr><td>n次查询，大数据量情况</td> <td>O(n<sup>2</sup>)</td> <td>$O(nlogn)$</td></tr></tbody></table> <p>正是因为上面，朴素算法的大规模数据区间和查询复杂度太高了，所以引入了“树状数组”这种数据结构来降低复杂度。</p> <h3 id="_1-2-前置知识-lowbit-操作"><a href="#_1-2-前置知识-lowbit-操作" class="header-anchor">#</a> 1.2.前置知识- lowbit()操作</h3> <p>lowbit()操作：</p> <ul><li>它表示非负整数在二进制表示下最低位1和后面的0构成的十进制数值</li></ul> <p><code>eg. lowbit(44)</code>=lowbit( (101<strong>100</strong>)<sub>2</sub> )=(<strong>100</strong>)<sub>2</sub>=4</p> <ul><li><p>由位运算容易知道：</p></li> <li><div class="language-txt line-numbers-mode"><pre class="language-text"><code>101100
010011
加一
010100
然后，按位&amp;
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br></div></div></li></ul> <p>$lowbit(n)= n&amp;( (~n)+1 ) = n&amp;( ~n+1 )$</p> <p>此外，因为计算机存储使用的是补码，取反加一后获得的是负的这个值。
<code>~n+1=-n</code></p> <p>所以，<code>lowbit(n)=n&amp;(-n)</code></p> <h3 id="_1-3-树状数组–思想及实现"><a href="#_1-3-树状数组–思想及实现" class="header-anchor">#</a> 1.3.树状数组–思想及实现</h3> <p>由于求的是“区间和查询”-》想到-》前缀和相减的方法-》使用树形结构来维护，就会把复杂度降到$O(logn)$</p> <p>对于一个序列，我们在其上建立一个这样的森林结构：
<font size="3" style="background:yellow;">每个节点t[x]保存以x为根的子树中叶节点值的和</font></p> <p><img src="https://cdn.jsdelivr.net/gh/HACV/picture/img/%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%8401.png" alt="树状数组01"></p> <ul><li>问题：</li> <li>那么每个节点覆盖的长度是多少呢？</li></ul> <h4 id="_1、观察1"><a href="#_1、观察1" class="header-anchor">#</a> 1、观察1</h4> <p>把每个节点<code>t[x]</code>的<code>x</code>转化为二进制后</p> <p><img src="https://cdn.jsdelivr.net/gh/HACV/picture/img/%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84%E4%BA%8C%E8%BF%9B%E5%88%B6%E8%A7%82%E5%AF%9F02.png" alt="树状数组二进制观察02"></p> <p><font size="3" style="background:yellow;">我们会发现每一层的<strong>末尾的零</strong>的个数都是相同的（我用红色箭头标记了）</font></p> <h4 id="_2、观察2"><a href="#_2、观察2" class="header-anchor">#</a> 2、观察2</h4> <p>进一步观察知道：<strong>t[x]节点覆盖的长度就是lowbit(x)</strong> <img src="https://cdn.jsdelivr.net/gh/HACV/picture/img/%E6%95%B0%E7%BB%84%E6%95%B0%E7%BB%84%E5%92%8Clowbit03.png" alt="数组数组和lowbit03"></p> <p><font size="3" style="background:yellow;">1、t[x]节点的父节点为t[x + lowbit(x)] </font> <font size="3" style="background:yellow;">2、整颗树的高度为$logn+1$ </font></p> <h4 id="_3、归纳出公式"><a href="#_3、归纳出公式" class="header-anchor">#</a> 3、归纳出公式</h4> <p><img src="https://cdn.jsdelivr.net/gh/HACV/picture/img/%E6%95%B0%E7%BB%84%E6%95%B0%E7%BB%84%E5%85%AC%E5%BC%8F04.png" alt="数组数组公式04"></p> <h4 id="_4、代码，add-n-k"><a href="#_4、代码，add-n-k" class="header-anchor">#</a> 4、代码，add(n,k)</h4> <p>向x号位置进行加k</p> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">void</span> <span class="token function">add</span><span class="token punctuation">(</span><span class="token keyword">int</span> x<span class="token punctuation">,</span> <span class="token keyword">int</span> k<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token comment">//for(; x&lt;=n; x+=lowbit(x) )</span>
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token punctuation">;</span> x<span class="token operator">&lt;=</span>n<span class="token punctuation">;</span> x<span class="token operator">+=</span><span class="token punctuation">(</span> x<span class="token operator">&amp;</span><span class="token punctuation">(</span><span class="token operator">-</span>x<span class="token punctuation">)</span> <span class="token punctuation">)</span> <span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
    	t<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token operator">+=</span>k<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br></div></div><h4 id="_5、ask操作（核心）"><a href="#_5、ask操作（核心）" class="header-anchor">#</a> 5、ask操作（核心）</h4> <ul><li>查询这个点的前缀和，需要从这个点<strong>向左上</strong>找到上一个节点，<strong>并加上其节点</strong>的值</li></ul> <p><img src="https://cdn.jsdelivr.net/gh/HACV/picture/img/%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84ask%E6%93%8D%E4%BD%9C05.png" alt="树状数组ask操作05"></p> <h4 id="再次观察"><a href="#再次观察" class="header-anchor">#</a> 再次观察</h4> <p>可以发现向左上找上一个节点只需要将<code>下标-=lowbit(这个节点的下标)</code></p> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code>
<span class="token keyword">int</span> <span class="token function">ask</span><span class="token punctuation">(</span><span class="token keyword">int</span> x<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token keyword">int</span> rt<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
	<span class="token comment">//for(; x ; x-=lowbit(x) )</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token punctuation">;</span> x <span class="token punctuation">;</span> x<span class="token operator">-=</span><span class="token punctuation">(</span> x<span class="token operator">&amp;</span><span class="token punctuation">(</span><span class="token operator">-</span>x<span class="token punctuation">)</span> <span class="token punctuation">)</span> <span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
    	rt<span class="token operator">+=</span>t<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    
    <span class="token keyword">return</span> rt<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br></div></div><p>然后，如果我们要求区间和，我们可以分别求出前缀和，并相减。</p> <h3 id="_1-4-树状数组的扩展应用"><a href="#_1-4-树状数组的扩展应用" class="header-anchor">#</a> 1.4.树状数组的扩展应用</h3> <p>树状数组-》是一个动态维护前缀和的工具-》我们需要灵活应用它</p> <ul><li>（1）单点修改+区间查询（前面的例子）</li> <li>（2）区间修改，单点查询</li> <li>（3）区间修改，区间查询等操作</li></ul> <h4 id="_2、区间修改，单点查询"><a href="#_2、区间修改，单点查询" class="header-anchor">#</a> 2、区间修改，单点查询</h4> <p>（5分钟）</p> <p>（6分20）</p> <h4 id="数组→树状数组→前缀区间维护→和、异或和、最大值、最小值"><a href="#数组→树状数组→前缀区间维护→和、异或和、最大值、最小值" class="header-anchor">#</a> 数组→树状数组→前缀区间维护→和、异或和、最大值、最小值</h4> <p>对于一个序列我们可以根据其建立一个树状数组去维护其<strong>前缀区间</strong>
注意：
其维护的值不只有和。
异或和，最大值，最小值等。</p> <h4 id="而对于区间修改，区间查询这样复杂的区间操作"><a href="#而对于区间修改，区间查询这样复杂的区间操作" class="header-anchor">#</a> 而对于区间修改，区间查询这样复杂的区间操作</h4> <p>复杂区间问题，使用树状数组就不是很方便了。
我们可以转而使用**扩展性更强的“线段树”**来进行区间维护。</p> <h3 id="_1-5-总结与代码"><a href="#_1-5-总结与代码" class="header-anchor">#</a> 1.5.总结与代码</h3> <ul><li>代码总结</li></ul> <h2 id="_02-线段树⭐️"><a href="#_02-线段树⭐️" class="header-anchor">#</a> 02.线段树⭐️</h2> <ul><li><p><a href="https://www.bilibili.com/video/BV1cb411t7AM" target="_blank" rel="noopener noreferrer">参考B站传送门<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></p></li> <li><p>假设，我现在拿到了一个非常非常大的数组，对于这个数组里面的数字呢，我们需要反反复复的不断进行两个操。</p></li> <li><p>（1）query，不断的随机选一块区间，要求把这个区间里面的所有数字都加起来。</p></li> <li><p>（2）update，不断的修改这个数组里面的某一个值。</p></li></ul> <p>将query从$O(n)$降低到$O(1)$，用<strong>前缀和数组</strong>（sum_arr）prefix</p> <ul><li>优点：query从$O(n)$降低到$O(1)$，</li> <li>缺点：update从从$O(1)$升到$O(n)$，
所以，如果我的query和update非常多的话，不论我用什么方法，总体的速度都不会特别的快。</li></ul> <p>我们讨论的线段树，可以稍微把这两个操作的速度平均一下，使得两者的时间都落在$O(logn)$上面
从而，增加整个算法的效率。</p> <h3 id="_2-1-线段树的基本概念"><a href="#_2-1-线段树的基本概念" class="header-anchor">#</a> 2.1.线段树的基本概念</h3> <ul><li>1、线段树是树</li> <li>2、根上的数字表示：整个数组一直从0到最后一个数字，这段区间加起来等于多少，比如<code>[0,n-1]</code>区间</li> <li>3、根的左边和右边子节点分别表示：</li> <li>左边：<code>[left , (left+right)/2 ]</code>（注意是C语言中的整除）</li> <li>右边：<code>[(left+right)/2+1 , right ]</code></li> <li>4、比如，根节点为<code>[0 , 2]</code>，那么左边子树<code>[0 ,1 ]</code>，右边是<code>[2 , 2]</code>也就是<code>[2]</code></li> <li>5、所有叶子节点，正好都是这个数组中单个元素的数字。</li></ul> <h4 id="_2-1-1-查询"><a href="#_2-1-1-查询" class="header-anchor">#</a> 2.1.1.查询</h4> <h4 id="_2-1-2-更新"><a href="#_2-1-2-更新" class="header-anchor">#</a> 2.1.2.更新</h4> <p>先查询到，然后从下往上进行更新。</p> <h4 id="_2-1-3-存储结构"><a href="#_2-1-3-存储结构" class="header-anchor">#</a> 2.1.3.存储结构</h4> <p>用近似的完全二叉树，用“虚点”</p> <ul><li>线段树01</li></ul> <p><img src="https://cdn.jsdelivr.net/gh/HACV/picture/img/%E7%BA%BF%E6%AE%B5%E6%A0%9101.png" alt="线段树01"></p> <ul><li>线段树02</li></ul> <p><img src="https://cdn.jsdelivr.net/gh/HACV/picture/img/%E7%BA%BF%E6%AE%B5%E6%A0%9102.png" alt="线段树02"></p> <p>如上图，这样的“静态存储”方式，显然容易用类似于“堆排序”的方式控制</p> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>left_node=2*node+1
right_node=2*node+2
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p>tree数组：我们现在给tree的下标都加上node
arr数组：所有不写node的start、end、L、R都是arr数组的下标</p> <p>自己在做的时候，大家一个个计算一下树大概需要多少节点。</p> <h4 id="_2-1-4-递归代码"><a href="#_2-1-4-递归代码" class="header-anchor">#</a> 2.1.4.递归代码</h4> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;bits/stdc++.h&gt;</span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

<span class="token keyword">const</span> <span class="token keyword">int</span> MAX_LEN<span class="token operator">=</span><span class="token number">1000</span><span class="token punctuation">;</span>


<span class="token comment">//node为tree的节点，L到R是要建立的范围 </span>
<span class="token keyword">void</span> <span class="token function">build_tree</span><span class="token punctuation">(</span><span class="token keyword">int</span> arr<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">int</span> tree<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">int</span> node<span class="token punctuation">,</span> <span class="token keyword">int</span> start <span class="token punctuation">,</span><span class="token keyword">int</span> end<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	
	<span class="token keyword">if</span><span class="token punctuation">(</span> start<span class="token operator">==</span>end <span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		tree<span class="token punctuation">[</span>node<span class="token punctuation">]</span><span class="token operator">=</span>arr<span class="token punctuation">[</span>start<span class="token punctuation">]</span><span class="token punctuation">;</span><span class="token comment">//end也行</span>
		<span class="token keyword">return</span> <span class="token punctuation">;</span> 
	<span class="token punctuation">}</span>
	 
	<span class="token keyword">int</span> mid<span class="token operator">=</span><span class="token punctuation">(</span>start<span class="token operator">+</span>end<span class="token punctuation">)</span><span class="token operator">/</span><span class="token number">2</span><span class="token punctuation">;</span>
	<span class="token keyword">int</span> left_node<span class="token operator">=</span><span class="token number">2</span><span class="token operator">*</span>node<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span>
	<span class="token keyword">int</span> right_node<span class="token operator">=</span><span class="token number">2</span><span class="token operator">*</span>node<span class="token operator">+</span><span class="token number">2</span><span class="token punctuation">;</span>
	
	<span class="token comment">//由于是递归，所以我们要准备一个出口。</span>
	 
	<span class="token function">build_tree</span><span class="token punctuation">(</span>arr<span class="token punctuation">,</span>tree<span class="token punctuation">,</span>left_node<span class="token punctuation">,</span>start<span class="token punctuation">,</span>mid<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token function">build_tree</span><span class="token punctuation">(</span>arr<span class="token punctuation">,</span>tree<span class="token punctuation">,</span>right_node<span class="token punctuation">,</span>mid<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>end<span class="token punctuation">)</span><span class="token punctuation">;</span>
	
	tree<span class="token punctuation">[</span>node<span class="token punctuation">]</span><span class="token operator">=</span> tree<span class="token punctuation">[</span>left_node<span class="token punctuation">]</span><span class="token operator">+</span>tree<span class="token punctuation">[</span>right_node<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>


<span class="token comment">//修改arr[idx]=val，然后导致分支也要修改 </span>
<span class="token keyword">void</span> <span class="token function">update_tree</span><span class="token punctuation">(</span><span class="token keyword">int</span> arr<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">int</span> tree<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">int</span> node<span class="token punctuation">,</span> <span class="token keyword">int</span> start <span class="token punctuation">,</span><span class="token keyword">int</span> end<span class="token punctuation">,</span> <span class="token keyword">int</span> idx<span class="token punctuation">,</span> <span class="token keyword">int</span> val<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token keyword">if</span><span class="token punctuation">(</span> start<span class="token operator">==</span>end <span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		arr<span class="token punctuation">[</span>idx<span class="token punctuation">]</span><span class="token operator">=</span>val<span class="token punctuation">;</span>
		tree<span class="token punctuation">[</span>node<span class="token punctuation">]</span><span class="token operator">=</span>val<span class="token punctuation">;</span>
		<span class="token keyword">return</span> <span class="token punctuation">;</span>
	<span class="token punctuation">}</span>
	
	<span class="token keyword">int</span> mid<span class="token operator">=</span><span class="token punctuation">(</span>start<span class="token operator">+</span>end<span class="token punctuation">)</span><span class="token operator">/</span><span class="token number">2</span><span class="token punctuation">;</span>
	<span class="token keyword">int</span> left_node<span class="token operator">=</span><span class="token number">2</span><span class="token operator">*</span>node<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span>
	<span class="token keyword">int</span> right_node<span class="token operator">=</span><span class="token number">2</span><span class="token operator">*</span>node<span class="token operator">+</span><span class="token number">2</span><span class="token punctuation">;</span>
	
	<span class="token comment">//落在左分支 </span>
	<span class="token keyword">if</span><span class="token punctuation">(</span> idx<span class="token operator">&gt;=</span>start <span class="token operator">&amp;&amp;</span> idx<span class="token operator">&lt;=</span>mid <span class="token punctuation">)</span> 
	<span class="token punctuation">{</span>
		<span class="token function">update_tree</span><span class="token punctuation">(</span>arr<span class="token punctuation">,</span>tree<span class="token punctuation">,</span>left_node<span class="token punctuation">,</span>start<span class="token punctuation">,</span>mid<span class="token punctuation">,</span>idx<span class="token punctuation">,</span>val<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>
	<span class="token keyword">else</span>
	<span class="token punctuation">{</span>
		<span class="token function">update_tree</span><span class="token punctuation">(</span>arr<span class="token punctuation">,</span>tree<span class="token punctuation">,</span>right_node<span class="token punctuation">,</span>mid<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>end<span class="token punctuation">,</span>idx<span class="token punctuation">,</span>val<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>
	
	<span class="token comment">//更新 </span>
	tree<span class="token punctuation">[</span>node<span class="token punctuation">]</span><span class="token operator">=</span> tree<span class="token punctuation">[</span>left_node<span class="token punctuation">]</span><span class="token operator">+</span>tree<span class="token punctuation">[</span>right_node<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>


<span class="token keyword">int</span> <span class="token function">query_tree</span><span class="token punctuation">(</span><span class="token keyword">int</span> arr<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">int</span> tree<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">int</span> node<span class="token punctuation">,</span> <span class="token keyword">int</span> start <span class="token punctuation">,</span><span class="token keyword">int</span> end<span class="token punctuation">,</span> <span class="token keyword">int</span> L<span class="token punctuation">,</span> <span class="token keyword">int</span> R<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token comment">//不在计算范围之内，返回0</span>
	<span class="token keyword">if</span><span class="token punctuation">(</span> R<span class="token operator">&lt;</span>start <span class="token operator">||</span> L<span class="token operator">&gt;</span>end <span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>
	<span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span> L<span class="token operator">&lt;=</span>start <span class="token operator">&amp;&amp;</span> end<span class="token operator">&lt;=</span>R <span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token keyword">return</span> tree<span class="token punctuation">[</span>node<span class="token punctuation">]</span><span class="token punctuation">;</span><span class="token comment">//减枝 </span>
	<span class="token punctuation">}</span>
	<span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span> start<span class="token operator">==</span>end <span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token keyword">return</span> tree<span class="token punctuation">[</span>node<span class="token punctuation">]</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>
	<span class="token keyword">else</span>
	<span class="token punctuation">{</span>
		<span class="token comment">//要分割区间</span>
		<span class="token keyword">int</span> mid<span class="token operator">=</span><span class="token punctuation">(</span>start<span class="token operator">+</span>end<span class="token punctuation">)</span><span class="token operator">/</span><span class="token number">2</span><span class="token punctuation">;</span>
		<span class="token keyword">int</span> left_node<span class="token operator">=</span><span class="token number">2</span><span class="token operator">*</span>node<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span>
		<span class="token keyword">int</span> right_node<span class="token operator">=</span><span class="token number">2</span><span class="token operator">*</span>node<span class="token operator">+</span><span class="token number">2</span><span class="token punctuation">;</span>
		
		<span class="token keyword">int</span> sum_left<span class="token operator">=</span><span class="token function">query_tree</span><span class="token punctuation">(</span>arr<span class="token punctuation">,</span>tree<span class="token punctuation">,</span>left_node<span class="token punctuation">,</span>start<span class="token punctuation">,</span>mid<span class="token punctuation">,</span>L<span class="token punctuation">,</span>R<span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token keyword">int</span> sum_right<span class="token operator">=</span><span class="token function">query_tree</span><span class="token punctuation">(</span>arr<span class="token punctuation">,</span>tree<span class="token punctuation">,</span>right_node<span class="token punctuation">,</span>mid<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>end<span class="token punctuation">,</span>L<span class="token punctuation">,</span>R<span class="token punctuation">)</span><span class="token punctuation">;</span>
		
		<span class="token keyword">return</span> sum_left<span class="token operator">+</span>sum_right<span class="token punctuation">;</span> 
	<span class="token punctuation">}</span>
	
<span class="token punctuation">}</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token keyword">int</span> arr<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token operator">=</span><span class="token punctuation">{</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">3</span><span class="token punctuation">,</span><span class="token number">5</span><span class="token punctuation">,</span><span class="token number">7</span><span class="token punctuation">,</span><span class="token number">9</span><span class="token punctuation">,</span><span class="token number">11</span><span class="token punctuation">}</span><span class="token punctuation">;</span>
	<span class="token keyword">int</span> size<span class="token operator">=</span><span class="token number">6</span><span class="token punctuation">;</span>
	
	<span class="token keyword">int</span> tree<span class="token punctuation">[</span>MAX_LEN<span class="token punctuation">]</span><span class="token operator">=</span><span class="token punctuation">{</span><span class="token number">0</span><span class="token punctuation">}</span><span class="token punctuation">;</span> 
	
	<span class="token comment">//0表示根节点 </span>
	<span class="token function">build_tree</span><span class="token punctuation">(</span>arr<span class="token punctuation">,</span>tree<span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span>size<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	
<span class="token comment">//	for(int i=0; i&lt;15;++i)</span>
<span class="token comment">//	{</span>
<span class="token comment">//		cout&lt;&lt;tree[i]&lt;&lt;endl;</span>
<span class="token comment">//	}</span>
	
	<span class="token function">update_tree</span><span class="token punctuation">(</span>arr<span class="token punctuation">,</span>tree<span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span>size<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">4</span><span class="token punctuation">,</span><span class="token number">6</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	
	<span class="token keyword">int</span> s<span class="token operator">=</span><span class="token function">query_tree</span><span class="token punctuation">(</span>arr<span class="token punctuation">,</span>tree<span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span>size<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">5</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	cout<span class="token operator">&lt;&lt;</span>s<span class="token operator">&lt;&lt;</span>endl<span class="token punctuation">;</span>
	
	<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br><span class="line-number">61</span><br><span class="line-number">62</span><br><span class="line-number">63</span><br><span class="line-number">64</span><br><span class="line-number">65</span><br><span class="line-number">66</span><br><span class="line-number">67</span><br><span class="line-number">68</span><br><span class="line-number">69</span><br><span class="line-number">70</span><br><span class="line-number">71</span><br><span class="line-number">72</span><br><span class="line-number">73</span><br><span class="line-number">74</span><br><span class="line-number">75</span><br><span class="line-number">76</span><br><span class="line-number">77</span><br><span class="line-number">78</span><br><span class="line-number">79</span><br><span class="line-number">80</span><br><span class="line-number">81</span><br><span class="line-number">82</span><br><span class="line-number">83</span><br><span class="line-number">84</span><br><span class="line-number">85</span><br><span class="line-number">86</span><br><span class="line-number">87</span><br><span class="line-number">88</span><br><span class="line-number">89</span><br><span class="line-number">90</span><br><span class="line-number">91</span><br><span class="line-number">92</span><br><span class="line-number">93</span><br><span class="line-number">94</span><br><span class="line-number">95</span><br><span class="line-number">96</span><br><span class="line-number">97</span><br><span class="line-number">98</span><br><span class="line-number">99</span><br><span class="line-number">100</span><br><span class="line-number">101</span><br><span class="line-number">102</span><br><span class="line-number">103</span><br><span class="line-number">104</span><br><span class="line-number">105</span><br><span class="line-number">106</span><br><span class="line-number">107</span><br><span class="line-number">108</span><br><span class="line-number">109</span><br><span class="line-number">110</span><br></div></div><p><a href="https://www.bilibili.com/video/BV1xE411W7Vn" target="_blank" rel="noopener noreferrer">B站传送门<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></p> <ul><li>这应该是全网<strong>二维线段树</strong>讲的最好的了，兹磁up</li></ul> <h3 id="_2-2-一维线段树"><a href="#_2-2-一维线段树" class="header-anchor">#</a> 2.2.一维线段树</h3> <ul><li>前置知识：递归，基本二叉树</li></ul> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>让我们想一个问题
luogu P3372【模板】线段树1
如题，已知一个数列，你需要进行下面两种操作将某区间每一个数加上k
求出某区间每一个数的和
70%: 1 ≤ n ≤ 10^3，1 ≤ m s 10^4
100%: 1 s n,m ≤ 10^5
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br></div></div><ul><li>暴力做法
时间复杂度$o(nm)$显然爆炸
需要$o(mlogn)$的做法</li></ul> <h4 id="（1）需要线段树-一维线段树"><a href="#（1）需要线段树-一维线段树" class="header-anchor">#</a> （1）需要线段树(一维线段树)</h4> <p>思路：</p> <ul><li>我们不想一—枚举每一个元素</li> <li>我们希望存储区间信息(维护区间,而非单点)
如图，这样，在线段树中，<strong>每一个节点都维护了一个区间</strong>。</li> <li>线段树是一棵二叉树，叶子节点是数列元素</li> <li>二分法</li></ul> <h4 id="（2）一些变量的定义"><a href="#（2）一些变量的定义" class="header-anchor">#</a> （2）一些变量的定义</h4> <p>o:当前节点
lson (lson=o<em>2):左儿子
rson (rson=o</em>2+1):右儿子
这些都是二叉树的性质
mid ((1+r)/2):区间中点，左边是左儿子的区间，右边是右儿子的区间</p> <h4 id="（3）基本操作1-上推update"><a href="#（3）基本操作1-上推update" class="header-anchor">#</a> （3）基本操作1:上推update</h4> <p>在线段树中，我们希望父亲节点存储两个儿子节点的区间信息
这就需要用两个儿子的信息去更新父亲的信息这个操作就是上推update</p> <p>上推的部分代码如下：</p> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">struct</span> <span class="token class-name">segtree</span>
<span class="token punctuation">{</span> 
    <span class="token comment">//线段树</span>
    <span class="token keyword">int</span> sum<span class="token punctuation">,</span>mx<span class="token punctuation">;</span><span class="token comment">//区间和，区间最大值</span>
<span class="token punctuation">}</span>dat<span class="token punctuation">[</span> <span class="token number">100005</span><span class="token operator">&lt;&lt;</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">;</span><span class="token comment">//空间需要开元素个数的4倍,开4倍是为了给上边的根、父亲节点预留空间。</span>

<span class="token keyword">void</span> <span class="token function">update</span><span class="token punctuation">(</span><span class="token keyword">int</span> o<span class="token punctuation">)</span><span class="token comment">//更新当前节点的信息</span>
<span class="token punctuation">{</span>
    dat<span class="token punctuation">[</span>o<span class="token punctuation">]</span><span class="token punctuation">.</span>sum <span class="token operator">=</span> dat<span class="token punctuation">[</span>lson<span class="token punctuation">]</span><span class="token punctuation">.</span>sum<span class="token operator">+</span>dat<span class="token punctuation">[</span>rson<span class="token punctuation">]</span><span class="token punctuation">.</span>sum<span class="token punctuation">;</span>
    dat<span class="token punctuation">[</span>o<span class="token punctuation">]</span><span class="token punctuation">.</span>mx <span class="token operator">=</span> <span class="token function">max</span><span class="token punctuation">(</span> dat<span class="token punctuation">[</span> lson<span class="token punctuation">]</span><span class="token punctuation">.</span>mx <span class="token punctuation">,</span> dat<span class="token punctuation">[</span>rson<span class="token punctuation">]</span><span class="token punctuation">.</span>mx <span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br></div></div><h4 id="（4）基本操作2-询问query"><a href="#（4）基本操作2-询问query" class="header-anchor">#</a> （4）基本操作2:询问query</h4> <p>对于线段树的题目来说，每个题目都会有询问。</p> <p>每一次询问，我们只需要访问到完全包含在询问区间里的节点即可
每一次询问，访问最多logn个节点
时间复杂度O( logn)</p> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">int</span> <span class="token function">query</span><span class="token punctuation">(</span><span class="token keyword">int</span> o<span class="token punctuation">,</span><span class="token keyword">int</span> l<span class="token punctuation">,</span><span class="token keyword">int</span> r<span class="token punctuation">,</span><span class="token keyword">int</span> ql<span class="token punctuation">,</span><span class="token keyword">int</span> qr<span class="token punctuation">)</span><span class="token comment">//o:当前节点， l,r:对应区间</span>
<span class="token punctuation">{</span> 	

	<span class="token comment">//[1,r]内对应询问区间的和,注意，这是减枝用的。</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token operator">&gt;=</span>q1 <span class="token operator">&amp;&amp;</span>r<span class="token operator">&lt;=</span>qr<span class="token punctuation">)</span><span class="token comment">//如果询问区间包含当前区间，直接返回</span>
    	<span class="token keyword">return</span> dat<span class="token punctuation">[</span>o<span class="token punctuation">]</span><span class="token punctuation">.</span>sum<span class="token punctuation">;</span>
        
    
    <span class="token keyword">int</span> res<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span><span class="token comment">//下面是不包含的情况</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>ql<span class="token operator">&lt;=</span>mid<span class="token punctuation">)</span><span class="token comment">//如果询问区间在左儿子有，就把左儿子内对应区间和加上</span>
    <span class="token punctuation">{</span>
    	res <span class="token operator">+=</span><span class="token function">query</span><span class="token punctuation">(</span>lson<span class="token punctuation">,</span>l<span class="token punctuation">,</span>mid<span class="token punctuation">,</span>ql<span class="token punctuation">,</span>qr<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    
    <span class="token keyword">if</span><span class="token punctuation">(</span>qr<span class="token operator">&gt;</span>mid<span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
    	res <span class="token operator">+=</span> <span class="token function">query</span><span class="token punctuation">(</span> rson<span class="token punctuation">,</span>mid<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>r<span class="token punctuation">,</span>ql<span class="token punctuation">,</span>qr<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    
    <span class="token keyword">return</span> res<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br></div></div><h4 id="（5）基本操作3-修改modify"><a href="#（5）基本操作3-修改modify" class="header-anchor">#</a> （5）基本操作3:修改modify</h4> <ul><li>我们需要对叶子节点修改</li> <li>所以==(暂时）==不能向修改一样访问logn个节点，或者说，我们只能单点修改</li> <li>但是我们发现一个性质:只要我们不访问这个节点，它是什么值与我们无关</li> <li>换句话说，访问到了，我们再去修改也不迟</li> <li>所以我们引入一个新概念︰<strong>懒标记1azytag</strong> <strong>懒惰标记</strong></li></ul> <p>懒惰标记是线段树里面的一个难点！！</p> <ul><li><p>在修改时，与询问一样，我们只需要访问到完全包含在询问区间里的节点即可</p></li> <li><p>然后我们在此节点上打上懒标记
如何打“懒惰标记”呢？比如，你要修改的值是2，那么你把这个节点懒标记，并且加上2就可以了。</p></li> <li><p>如果要递归访问它的左右儿子，则要先把懒标记下传
因为，如果询问的话，你不把懒标记下传，那你的左右儿子的信息没有更新，如果这个时候询问，那么答案就是错误的！</p></li> <li><p>形象的说：父亲更新儿子。</p></li> <li><p>这样,<strong>修改</strong>操作就可以像<strong>询问</strong>一样只访问$logn$个节点了</p></li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code>懒标记下传pushdown
<span class="token keyword">void</span> <span class="token function">pushdown</span><span class="token punctuation">(</span><span class="token keyword">int</span> o<span class="token punctuation">,</span><span class="token keyword">int</span> l<span class="token punctuation">,</span><span class="token keyword">int</span> r<span class="token punctuation">)</span><span class="token comment">//下传</span>
<span class="token punctuation">{</span>	
	<span class="token comment">//注意：在修改和询问中都需要有下传操作</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>dat<span class="token punctuation">[</span>o<span class="token punctuation">]</span><span class="token punctuation">.</span>laz<span class="token punctuation">)</span><span class="token comment">//如果打上了懒标记</span>
    <span class="token punctuation">{</span>
        dat<span class="token punctuation">[</span>lson<span class="token punctuation">]</span><span class="token punctuation">.</span>sum <span class="token operator">+=</span> dat<span class="token punctuation">[</span>o<span class="token punctuation">]</span><span class="token punctuation">.</span>laz<span class="token operator">*</span><span class="token punctuation">(</span>mid<span class="token operator">-</span><span class="token number">1</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment">//懒标记*区间大小，用乘法分配率</span>
        dat<span class="token punctuation">[</span>rson<span class="token punctuation">]</span><span class="token punctuation">.</span>sum <span class="token operator">+=</span> dat<span class="token punctuation">[</span>o<span class="token punctuation">]</span><span class="token punctuation">.</span>laz<span class="token operator">*</span><span class="token punctuation">(</span>r<span class="token operator">-</span>mid<span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment">//更新左右儿子的区间信息</span>
        
        dat<span class="token punctuation">[</span>lson<span class="token punctuation">]</span><span class="token punctuation">.</span>laz<span class="token operator">+=</span>v<span class="token punctuation">;</span>
        dat<span class="token punctuation">[</span>rson<span class="token punctuation">]</span><span class="token punctuation">.</span>laz<span class="token operator">+=</span> v<span class="token punctuation">;</span> <span class="token comment">//下传左右儿子的懒标记，可以继续下传</span>
    <span class="token punctuation">}</span>
    
    dat<span class="token punctuation">[</span>o<span class="token punctuation">]</span><span class="token punctuation">.</span>laz <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token comment">//下传完了，自己的懒标记要清零</span>
<span class="token punctuation">}</span>

</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br></div></div><p>修改函数</p> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">void</span> <span class="token function">modify</span><span class="token punctuation">(</span><span class="token keyword">int</span> o<span class="token punctuation">,</span><span class="token keyword">int</span> l<span class="token punctuation">,</span><span class="token keyword">int</span> r<span class="token punctuation">,</span><span class="token keyword">int</span> ql<span class="token punctuation">,</span><span class="token keyword">int</span> qr<span class="token punctuation">,</span><span class="token keyword">int</span> v<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token operator">&gt;=</span>ql <span class="token operator">&amp;&amp;</span> r<span class="token operator">&lt;=</span>qr<span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        dat<span class="token punctuation">[</span>o<span class="token punctuation">]</span><span class="token punctuation">.</span>sum <span class="token operator">+=</span> v<span class="token operator">*</span><span class="token punctuation">(</span>r<span class="token operator">-</span><span class="token number">1</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment">//修改当前节点区间信息</span>
        dat<span class="token punctuation">[</span>o<span class="token punctuation">]</span><span class="token punctuation">.</span>laz <span class="token operator">+=</span> v<span class="token punctuation">;</span><span class="token comment">//更新懒标记，为了下传</span>
        <span class="token keyword">return</span> <span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token function">pushdown</span><span class="token punctuation">(</span>o<span class="token punctuation">,</span>l<span class="token punctuation">,</span>r<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">//下传</span>
    
    <span class="token keyword">if</span><span class="token punctuation">(</span>ql<span class="token operator">&lt;=</span>mid<span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
    	<span class="token function">modify</span><span class="token punctuation">(</span> lson<span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span>mid<span class="token punctuation">,</span>ql<span class="token punctuation">,</span>qr<span class="token punctuation">,</span>v<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    
    <span class="token keyword">if</span><span class="token punctuation">(</span>qr<span class="token operator">&gt;</span>mid<span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
    	 <span class="token function">modify</span><span class="token punctuation">(</span>rson<span class="token punctuation">,</span>mid<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>r<span class="token punctuation">,</span>ql<span class="token punctuation">,</span>qr<span class="token punctuation">,</span>v<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
   
    <span class="token function">update</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment">//因为有修改,注意要上推</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br></div></div><h4 id="（6）代码"><a href="#（6）代码" class="header-anchor">#</a> （6）代码</h4> <p>例题
luogu P3373【模板】线段树2（懒标记的优先级)这个题目，需要打2个懒惰标记
luogu SP1716 6SS3-Can you answer these queries III(最大子段和问题)
luogu SP2713 GSS4-can you answer these queries IV
luogu P4243 [3SoI2009]等差数列</p> <h3 id="_2-3-二维线段树"><a href="#_2-3-二维线段树" class="header-anchor">#</a> 2.3.二维线段树</h3> <ul><li>前置知识:—维线段树</li> <li>一维线段树可以处理<strong>数列</strong>上的区间问题，那么二维线段树就可以处理<strong>矩阵</strong>和<strong>子矩阵</strong>的问题</li></ul> <p>数列——一维
矩阵——二维</p> <p>实现方法</p> <ul><li>四分法</li></ul> <p>容易知道：一个线段——1分为2
一个矩阵，把每条边，1分为2，也就是分成4份了</p> <ul><li>实现方法
一个节点有4个儿子，每个儿子节点处理的是父亲矩阵的一个<strong>象限</strong>
每一次递归儿子节点时，需要把大矩阵的长和宽都一分为二，这样才能分成4份
二维线段树依然支持懒标记（下传操作)
让我们来敲代码
==没有找到模板题==
大家可以先按暂停，自己试试</li></ul> <p><strong>29分钟的时候的代码——51min</strong></p> <p>PS：此外，二维线段树还有另一种实现方法：
树套树实现！</p> <ul><li>但是树套树非常麻烦，而且在多维线段树里面，“树套树”一般用不了，不然码量巨大。</li> <li>还是“四份法”更加简单易懂。
这种做法相较于四分法更加麻烦，所以在这里就不讲了感兴趣的可以自己学一学
例题
luogu P4054luogu P3437luogu P3688</li></ul> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>多维线段树
三维线段树:八分法
四维线段树: 十六分法
一般不会考，一般就考到二维
因为2维，码量已经这么大了。
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br></div></div><h2 id="_03-主席树⭐️"><a href="#_03-主席树⭐️" class="header-anchor">#</a> 03.主席树⭐️</h2> <ul><li><a href="https://www.bilibili.com/video/BV1Vs411B7Da?from=search&seid=2203330248004294975" target="_blank" rel="noopener noreferrer">B站传送门<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li></ul> <h3 id="_3-1-主席树基础"><a href="#_3-1-主席树基础" class="header-anchor">#</a> 3.1.主席树基础</h3> <h3 id="（1）主席树基础"><a href="#（1）主席树基础" class="header-anchor">#</a> （1）主席树基础</h3> <ul><li><p>1、主席树——实际上是一个<strong>可持久化线段树</strong></p></li> <li><p>2、什么叫“可持久”的呢？就是特别坚持，它可以保存你的历史版本，</p></li> <li><p>比如说，有的题，要求你回到第K个操作啥的</p></li> <li><p>3、主席树还是“线段树”，所以前置知识点是会写线段树。</p></li> <li><p>4、主席树的目的就是保持它（线段树）的历史版本</p></li> <li><p>简单做法：给每个历史版本都开一个线段树对不对？空间可能会炸</p></li> <li><p>主席树，是一种升级，人们通过观察发现，每次单点修改，只会修改一条链的信息。（只会有入若干个节点被修改），那我们为什么要重新建树呢？我们只需把这3个节点重新建一遍就好了。</p></li></ul> <h3 id="（2）为什么叫“主席树”呢？"><a href="#（2）为什么叫“主席树”呢？" class="header-anchor">#</a> （2）为什么叫“主席树”呢？</h3> <ul><li>发明人：黄嘉泰，由于这3个字的首字母的缩写（HJT），同“胡锦涛”简写碰巧一致</li> <li>咳咳，不要查水表</li></ul> <p>时间：2.43</p> <p>title: 主席树
date: 2020-12-16 08:00:01</p> <h2 id="_04-设计跳表⭐"><a href="#_04-设计跳表⭐" class="header-anchor">#</a> 04.设计跳表⭐</h2> <ul><li>看Redis和kafka的时候会接触到“跳表”</li></ul> <h3 id="_4-1-跳表"><a href="#_4-1-跳表" class="header-anchor">#</a> 4.1.跳表</h3> <p>为了改善链表的查询时间复杂度。</p> <p>添加“索引”</p> <ul><li>一般来说上层节点个数应该是下层节点个数的<strong>二分之一</strong></li></ul> <h3 id="_4-2-添加节点"><a href="#_4-2-添加节点" class="header-anchor">#</a> 4.2.添加节点</h3> <p>添加到上一层的概率是二分之一之最简单的方武就是抛奥市</p> <p>所以我们让他在O和1之间随机如果是O就停止</p> <p>如果是1就继续</p> <p>最后正面础现的次数k，就代表我们要需要在第一层到k层之阃添加索引</p> <p>当然我们也不能能止他限增长</p> <p>所我们还需要加一个最大值的限制的</p> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">public</span> <span class="token keyword">int</span> <span class="token function">getRandom</span><span class="token punctuation">(</span><span class="token punctuation">)</span> 
<span class="token punctuation">{</span>
    <span class="token keyword">int</span> k<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>
    Random random <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token function">Random</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">while</span> <span class="token punctuation">(</span>random<span class="token punctuation">.</span><span class="token function">nextBoolean</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">&amp;&amp;</span>k<span class="token operator">&lt;</span>MAX_LEVEL<span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        k<span class="token operator">++</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
	<span class="token keyword">return</span> k<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br></div></div><p>字典树
2020-11-14 16:34:30</p> <h2 id="_05-trie-前缀树✅"><a href="#_05-trie-前缀树✅" class="header-anchor">#</a> 05.Trie-前缀树✅</h2> <ul><li><p>前缀树，又称字典树，是 N 叉树的特殊形式。</p></li> <li><p>Trie [traɪ] 读音和 try 相同，它的另一些名字有：<strong>字典树</strong>，<strong>前缀树</strong>，<strong>单词查找树</strong>等。</p></li> <li><p><a href="https://leetcode-cn.com/tag/trie/" target="_blank" rel="noopener noreferrer">LeetCode传送门<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></p></li></ul> <h3 id="_5-1-字典树类代码"><a href="#_5-1-字典树类代码" class="header-anchor">#</a> 5.1.字典树类代码</h3> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">class</span> <span class="token class-name">Trie</span> 
<span class="token punctuation">{</span>
<span class="token keyword">private</span><span class="token operator">:</span>
	<span class="token comment">//标记是否是单词结束</span>
    <span class="token keyword">bool</span> isEnd<span class="token punctuation">;</span>
    Trie<span class="token operator">*</span> next<span class="token punctuation">[</span><span class="token number">26</span><span class="token punctuation">]</span><span class="token punctuation">;</span>

<span class="token keyword">public</span><span class="token operator">:</span>
    <span class="token comment">/** Initialize your data structure here. */</span>
    <span class="token function">Trie</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        isEnd <span class="token operator">=</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
        <span class="token function">memset</span><span class="token punctuation">(</span>next<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> <span class="token keyword">sizeof</span><span class="token punctuation">(</span>next<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

	<span class="token comment">/** Inserts a word into the trie. */</span>
    <span class="token keyword">void</span> <span class="token function">insert</span><span class="token punctuation">(</span>string word<span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        Trie<span class="token operator">*</span> node <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">char</span> c <span class="token operator">:</span> word<span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token operator">-&gt;</span>next<span class="token punctuation">[</span>c<span class="token operator">-</span><span class="token string">'a'</span><span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token constant">NULL</span><span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                node<span class="token operator">-&gt;</span>next<span class="token punctuation">[</span>c<span class="token operator">-</span><span class="token string">'a'</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token function">Trie</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
            node <span class="token operator">=</span> node<span class="token operator">-&gt;</span>next<span class="token punctuation">[</span>c<span class="token operator">-</span><span class="token string">'a'</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        node<span class="token operator">-&gt;</span>isEnd <span class="token operator">=</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">/** Returns if the word is in the trie. */</span>
    <span class="token keyword">bool</span> <span class="token function">search</span><span class="token punctuation">(</span>string word<span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        Trie<span class="token operator">*</span> node <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">char</span> c <span class="token operator">:</span> word<span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            node <span class="token operator">=</span> node<span class="token operator">-&gt;</span>next<span class="token punctuation">[</span>c <span class="token operator">-</span> <span class="token string">'a'</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>node <span class="token operator">==</span> <span class="token constant">NULL</span><span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                <span class="token keyword">return</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
        <span class="token comment">//借助isEnd来看是不是最终的节点</span>
        <span class="token keyword">return</span> node<span class="token operator">-&gt;</span>isEnd<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">/** Returns if there is any word in the trie that starts with the given prefix. */</span>
    <span class="token keyword">bool</span> <span class="token function">startsWith</span><span class="token punctuation">(</span>string prefix<span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        Trie<span class="token operator">*</span> node <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">char</span> c <span class="token operator">:</span> prefix<span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            node <span class="token operator">=</span> node<span class="token operator">-&gt;</span>next<span class="token punctuation">[</span>c<span class="token operator">-</span><span class="token string">'a'</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>node <span class="token operator">==</span> <span class="token constant">NULL</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                <span class="token keyword">return</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>

        <span class="token comment">//比如，apple的前缀可以是app,apple</span>
        <span class="token keyword">return</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    
<span class="token punctuation">}</span><span class="token punctuation">;</span>

<span class="token comment">/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj-&gt;insert(word);
 * bool param_2 = obj-&gt;search(word);
 * bool param_3 = obj-&gt;startsWith(prefix);
 */</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br><span class="line-number">61</span><br><span class="line-number">62</span><br><span class="line-number">63</span><br><span class="line-number">64</span><br><span class="line-number">65</span><br><span class="line-number">66</span><br><span class="line-number">67</span><br><span class="line-number">68</span><br><span class="line-number">69</span><br><span class="line-number">70</span><br><span class="line-number">71</span><br></div></div><h2 id="_06-lru题解的衍生思考✅"><a href="#_06-lru题解的衍生思考✅" class="header-anchor">#</a> 06.LRU题解的衍生思考✅</h2> <h3 id="_6-1-文章意义"><a href="#_6-1-文章意义" class="header-anchor">#</a> 6.1.文章意义</h3> <ul><li>秋招进行到现在，面试手撕代码还是要写得又快又好才能冲击SP</li> <li>1、用STL的list双向链表，精简代码</li> <li>2、反思了一下，以前为什么C++设计的时候，迭代器有了end还要rbegin</li> <li>3、这类设计数据结构的方式让我们思考C语言的严版的设计方式和我们C++面向对象的设计方式的异同</li> <li>C++设计数据结构，感觉就是推广了C语言数据结构的设计方式，思维方式就很想this指针如何用C语言实现一样</li></ul> <p>//要使用<code>unorder_map</code>,它底层是散列，只会映射而不用排序,能够实现$O(1)$
//体现了STL中为什么，有end还要有rbegin的原因
//因为end指向的是指向最后一个元素的下一个节点，而rebgin体现的却是倒数第一个元素的位置</p> <h3 id="_6-2-ac代码"><a href="#_6-2-ac代码" class="header-anchor">#</a> 6.2.AC代码</h3> <ul><li><p><a href="https://leetcode-cn.com/problems/lru-cache/submissions/" target="_blank" rel="noopener noreferrer">1、LRU传送门<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></p></li> <li><p><a href="https://leetcode-cn.com/problems/lru-cache-lcci/" target="_blank" rel="noopener noreferrer">2、LRU传送门<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></p></li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">class</span> <span class="token class-name">LRUCache</span> <span class="token punctuation">{</span>
<span class="token keyword">private</span><span class="token operator">:</span>
    <span class="token keyword">struct</span> <span class="token class-name">node</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">int</span> key<span class="token punctuation">;</span>
        <span class="token keyword">int</span> val<span class="token punctuation">;</span>
        <span class="token function">node</span><span class="token punctuation">(</span><span class="token keyword">int</span> _key<span class="token punctuation">,</span> <span class="token keyword">int</span> _val<span class="token punctuation">)</span><span class="token operator">:</span> <span class="token function">key</span><span class="token punctuation">(</span>_key<span class="token punctuation">)</span> <span class="token punctuation">,</span> <span class="token function">val</span><span class="token punctuation">(</span>_val<span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
        <span class="token punctuation">}</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span><span class="token punctuation">;</span>
    
    list<span class="token operator">&lt;</span>node<span class="token operator">&gt;</span> DoubleList<span class="token punctuation">;</span>
    unordered_map<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token punctuation">,</span> list<span class="token operator">&lt;</span>node<span class="token operator">&gt;</span><span class="token operator">::</span>iterator<span class="token operator">&gt;</span> mp<span class="token punctuation">;</span>
    <span class="token keyword">int</span> cap<span class="token punctuation">;</span>

<span class="token keyword">public</span><span class="token operator">:</span>
    <span class="token function">LRUCache</span><span class="token punctuation">(</span><span class="token keyword">int</span> capacity<span class="token punctuation">)</span> 
    <span class="token punctuation">{</span>
        cap<span class="token operator">=</span>capacity<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    

    <span class="token keyword">int</span> <span class="token function">get</span><span class="token punctuation">(</span><span class="token keyword">int</span> key<span class="token punctuation">)</span> 
    <span class="token punctuation">{</span>
        <span class="token comment">//如果没有这个元素</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span> mp<span class="token punctuation">.</span><span class="token function">find</span><span class="token punctuation">(</span>key<span class="token punctuation">)</span><span class="token operator">==</span>mp<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">else</span>
        <span class="token punctuation">{</span>
            <span class="token keyword">int</span> ret<span class="token operator">=</span>mp<span class="token punctuation">[</span>key<span class="token punctuation">]</span><span class="token operator">-&gt;</span>val<span class="token punctuation">;</span>
            node <span class="token function">temp</span><span class="token punctuation">(</span>key<span class="token punctuation">,</span>ret<span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token comment">//如果有这个元素</span>
            DoubleList<span class="token punctuation">.</span><span class="token function">erase</span><span class="token punctuation">(</span> mp<span class="token punctuation">[</span>key<span class="token punctuation">]</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
            mp<span class="token punctuation">.</span><span class="token function">erase</span><span class="token punctuation">(</span> mp<span class="token punctuation">.</span><span class="token function">find</span><span class="token punctuation">(</span>key<span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>

            
            DoubleList<span class="token punctuation">.</span><span class="token function">push_front</span><span class="token punctuation">(</span>temp<span class="token punctuation">)</span><span class="token punctuation">;</span>
            mp<span class="token punctuation">[</span>key<span class="token punctuation">]</span><span class="token operator">=</span>DoubleList<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

            <span class="token keyword">return</span> ret<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    

    <span class="token keyword">void</span> <span class="token function">put</span><span class="token punctuation">(</span><span class="token keyword">int</span> key<span class="token punctuation">,</span> <span class="token keyword">int</span> value<span class="token punctuation">)</span> 
    <span class="token punctuation">{</span>
        node <span class="token function">temp</span><span class="token punctuation">(</span>key<span class="token punctuation">,</span>value<span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token comment">//有旧的节点，无论是不是和前面一样，都先删掉</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span> mp<span class="token punctuation">.</span><span class="token function">find</span><span class="token punctuation">(</span>key<span class="token punctuation">)</span><span class="token operator">!=</span>mp<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token comment">//先删掉</span>
            DoubleList<span class="token punctuation">.</span><span class="token function">erase</span><span class="token punctuation">(</span> mp<span class="token punctuation">[</span>key<span class="token punctuation">]</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
            mp<span class="token punctuation">.</span><span class="token function">erase</span><span class="token punctuation">(</span> mp<span class="token punctuation">.</span><span class="token function">find</span><span class="token punctuation">(</span>key<span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>

            DoubleList<span class="token punctuation">.</span><span class="token function">push_front</span><span class="token punctuation">(</span>temp<span class="token punctuation">)</span><span class="token punctuation">;</span>
            mp<span class="token punctuation">[</span>key<span class="token punctuation">]</span><span class="token operator">=</span>DoubleList<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">else</span>
        <span class="token punctuation">{</span>
            <span class="token comment">//来的是新节点,如果满了</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span> DoubleList<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">==</span>cap <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                <span class="token keyword">int</span> num<span class="token operator">=</span>  DoubleList<span class="token punctuation">.</span><span class="token function">rbegin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-&gt;</span>key<span class="token punctuation">;</span>

                DoubleList<span class="token punctuation">.</span><span class="token function">pop_back</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                mp<span class="token punctuation">.</span><span class="token function">erase</span><span class="token punctuation">(</span> mp<span class="token punctuation">.</span><span class="token function">find</span><span class="token punctuation">(</span> num <span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
            
            <span class="token comment">//记得映射</span>
            DoubleList<span class="token punctuation">.</span><span class="token function">push_front</span><span class="token punctuation">(</span>temp<span class="token punctuation">)</span><span class="token punctuation">;</span>
            mp<span class="token punctuation">[</span>key<span class="token punctuation">]</span><span class="token operator">=</span>DoubleList<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        
    <span class="token punctuation">}</span>

<span class="token punctuation">}</span><span class="token punctuation">;</span>

<span class="token comment">/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj-&gt;get(key);
 * obj-&gt;put(key,value);
 */</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br><span class="line-number">61</span><br><span class="line-number">62</span><br><span class="line-number">63</span><br><span class="line-number">64</span><br><span class="line-number">65</span><br><span class="line-number">66</span><br><span class="line-number">67</span><br><span class="line-number">68</span><br><span class="line-number">69</span><br><span class="line-number">70</span><br><span class="line-number">71</span><br><span class="line-number">72</span><br><span class="line-number">73</span><br><span class="line-number">74</span><br><span class="line-number">75</span><br><span class="line-number">76</span><br><span class="line-number">77</span><br><span class="line-number">78</span><br><span class="line-number">79</span><br><span class="line-number">80</span><br><span class="line-number">81</span><br><span class="line-number">82</span><br><span class="line-number">83</span><br><span class="line-number">84</span><br><span class="line-number">85</span><br><span class="line-number">86</span><br><span class="line-number">87</span><br></div></div><h3 id="_6-3-原始尝试代码（也ac了）"><a href="#_6-3-原始尝试代码（也ac了）" class="header-anchor">#</a> 6.3.原始尝试代码（也AC了）</h3> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">class</span> <span class="token class-name">LRUCache</span> <span class="token punctuation">{</span>
<span class="token keyword">private</span><span class="token operator">:</span>
    <span class="token keyword">struct</span> <span class="token class-name">node</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">int</span> key<span class="token punctuation">;</span>
        <span class="token keyword">int</span> val<span class="token punctuation">;</span>
        <span class="token function">node</span><span class="token punctuation">(</span><span class="token keyword">int</span> _key<span class="token punctuation">,</span> <span class="token keyword">int</span> _val<span class="token punctuation">)</span><span class="token operator">:</span> <span class="token function">key</span><span class="token punctuation">(</span>_key<span class="token punctuation">)</span> <span class="token punctuation">,</span> <span class="token function">val</span><span class="token punctuation">(</span>_val<span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
        <span class="token punctuation">}</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span><span class="token punctuation">;</span>
    <span class="token comment">//STL之双向链表使用</span>
    <span class="token comment">//要使用unorder_map,它底层是散列，只会映射而不用排序</span>
    list<span class="token operator">&lt;</span>node<span class="token operator">&gt;</span> mylist<span class="token punctuation">;</span>
    unordered_map<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token punctuation">,</span> list<span class="token operator">&lt;</span>node<span class="token operator">&gt;</span><span class="token operator">::</span>iterator<span class="token operator">&gt;</span> mp<span class="token punctuation">;</span>
    <span class="token keyword">int</span> cap<span class="token punctuation">;</span>

<span class="token keyword">public</span><span class="token operator">:</span>
    <span class="token function">LRUCache</span><span class="token punctuation">(</span><span class="token keyword">int</span> capacity<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        cap<span class="token operator">=</span>capacity<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    

    <span class="token keyword">int</span> <span class="token function">get</span><span class="token punctuation">(</span><span class="token keyword">int</span> key<span class="token punctuation">)</span> <span class="token punctuation">{</span>

        <span class="token comment">//如果没有这个</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span> mp<span class="token punctuation">.</span><span class="token function">find</span><span class="token punctuation">(</span>key<span class="token punctuation">)</span><span class="token operator">==</span>mp<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">else</span>
        <span class="token punctuation">{</span>
            <span class="token keyword">int</span> ret<span class="token operator">=</span>mp<span class="token punctuation">[</span>key<span class="token punctuation">]</span><span class="token operator">-&gt;</span>val<span class="token punctuation">;</span>

            node <span class="token function">temp</span><span class="token punctuation">(</span>key<span class="token punctuation">,</span>ret<span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token comment">//如果有</span>
            mylist<span class="token punctuation">.</span><span class="token function">erase</span><span class="token punctuation">(</span> mp<span class="token punctuation">[</span>key<span class="token punctuation">]</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
            mp<span class="token punctuation">.</span><span class="token function">erase</span><span class="token punctuation">(</span> mp<span class="token punctuation">.</span><span class="token function">find</span><span class="token punctuation">(</span>key<span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>

            <span class="token comment">//能够直接插入，却不用调用put分情况的原因是：本来就有这个节点，并且没有满</span>

            <span class="token comment">//mylist.push_back(temp);</span>
            mylist<span class="token punctuation">.</span><span class="token function">push_front</span><span class="token punctuation">(</span>temp<span class="token punctuation">)</span><span class="token punctuation">;</span>
            mp<span class="token punctuation">[</span>key<span class="token punctuation">]</span><span class="token operator">=</span>mylist<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token comment">//mp[key]=mylist.end();</span>
            <span class="token keyword">return</span> ret<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    

    <span class="token keyword">void</span> <span class="token function">put</span><span class="token punctuation">(</span><span class="token keyword">int</span> key<span class="token punctuation">,</span> <span class="token keyword">int</span> value<span class="token punctuation">)</span> 
    <span class="token punctuation">{</span>
        node <span class="token function">temp</span><span class="token punctuation">(</span>key<span class="token punctuation">,</span>value<span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token comment">//有旧的节点，无论是不是和前面一样，都先删掉</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span> mp<span class="token punctuation">.</span><span class="token function">find</span><span class="token punctuation">(</span>key<span class="token punctuation">)</span><span class="token operator">!=</span>mp<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token comment">//先删掉</span>
            mylist<span class="token punctuation">.</span><span class="token function">erase</span><span class="token punctuation">(</span> mp<span class="token punctuation">[</span>key<span class="token punctuation">]</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
            mp<span class="token punctuation">.</span><span class="token function">erase</span><span class="token punctuation">(</span> mp<span class="token punctuation">.</span><span class="token function">find</span><span class="token punctuation">(</span>key<span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>

            mylist<span class="token punctuation">.</span><span class="token function">push_front</span><span class="token punctuation">(</span>temp<span class="token punctuation">)</span><span class="token punctuation">;</span>
            mp<span class="token punctuation">[</span>key<span class="token punctuation">]</span><span class="token operator">=</span>mylist<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">else</span>
        <span class="token punctuation">{</span>
            <span class="token comment">//来的是新节点,如果满了</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span> mylist<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">==</span>cap <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                <span class="token comment">//注意此处，体现了STL中为什么，有end还要有rbegin的原因</span>
       <span class="token comment">//因为end指向的是指向最后一个元素的下一个节点，而rebgin体现的却是倒数第一个元素的位置</span>
                <span class="token keyword">int</span> num<span class="token operator">=</span>  mylist<span class="token punctuation">.</span><span class="token function">rbegin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-&gt;</span>key<span class="token punctuation">;</span>

                <span class="token comment">//mylist.erase( mp[num] );</span>
                mylist<span class="token punctuation">.</span><span class="token function">pop_back</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                mp<span class="token punctuation">.</span><span class="token function">erase</span><span class="token punctuation">(</span> mp<span class="token punctuation">.</span><span class="token function">find</span><span class="token punctuation">(</span> num <span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
            
            mylist<span class="token punctuation">.</span><span class="token function">push_front</span><span class="token punctuation">(</span>temp<span class="token punctuation">)</span><span class="token punctuation">;</span>
            mp<span class="token punctuation">[</span>key<span class="token punctuation">]</span><span class="token operator">=</span>mylist<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            
        <span class="token punctuation">}</span>

        <span class="token comment">//记得映射</span>
       
       <span class="token keyword">return</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>


<span class="token punctuation">}</span><span class="token punctuation">;</span>

<span class="token comment">/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj-&gt;get(key);
 * obj-&gt;put(key,value);
 */</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br><span class="line-number">61</span><br><span class="line-number">62</span><br><span class="line-number">63</span><br><span class="line-number">64</span><br><span class="line-number">65</span><br><span class="line-number">66</span><br><span class="line-number">67</span><br><span class="line-number">68</span><br><span class="line-number">69</span><br><span class="line-number">70</span><br><span class="line-number">71</span><br><span class="line-number">72</span><br><span class="line-number">73</span><br><span class="line-number">74</span><br><span class="line-number">75</span><br><span class="line-number">76</span><br><span class="line-number">77</span><br><span class="line-number">78</span><br><span class="line-number">79</span><br><span class="line-number">80</span><br><span class="line-number">81</span><br><span class="line-number">82</span><br><span class="line-number">83</span><br><span class="line-number">84</span><br><span class="line-number">85</span><br><span class="line-number">86</span><br><span class="line-number">87</span><br><span class="line-number">88</span><br><span class="line-number">89</span><br><span class="line-number">90</span><br><span class="line-number">91</span><br><span class="line-number">92</span><br><span class="line-number">93</span><br><span class="line-number">94</span><br><span class="line-number">95</span><br><span class="line-number">96</span><br></div></div><h2 id="_07-字符串匹配算法⭐"><a href="#_07-字符串匹配算法⭐" class="header-anchor">#</a> 07.字符串匹配算法⭐</h2> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>——突破深信服字符串匹配——
字符串匹配之BF&amp;RK
字符串匹配暴力和hash优化
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div><ul><li><font face="楷体" color="red" size="5">单模式串匹配算法</font> <ul><li>也就是一个串和一个串进行匹配</li></ul></li> <li><b>BF算法</b>（Brute Force 的缩写，也叫暴力匹配算法，朴素匹配算法)</li></ul> <blockquote><ul><li>Brute adj. 蛮干不动脑筋的</li></ul></blockquote> <ul><li><b>RK算法</b>（Rabin-Karp 算法）</li></ul> <blockquote><ul><li>由它的两位发明者 Rabin 和 Karp 的名字来命名的</li></ul></blockquote> <ul><li><b>BM算法</b>（Boyer-Moore 算法）</li></ul> <blockquote><ul><li>它是一种非常高效的字符串匹配算法，有实验统计，它的性能是著名的KMP 算法的3到4倍。</li></ul></blockquote> <ul><li><b>KMP算法</b></li> <li><font face="楷体" color="red" size="5">多模式串匹配算法</font> <ul><li>是在一个串中同时查找多个串</li></ul></li> <li><b>Trie树</b>，（又称前缀树，字典树，单词查找树）</li> <li>Trie这个术语来自于retrieval根据词源学, trie的发明者Edward Fredkin把它读作/'tri:/ &quot;tree&quot;。但是 ,其他作者把它读作/'tra1/ &quot;try&quot;。</li> <li><b>AC自动机算法</b>（Aho–Corasick算法）是由Alfred V.Aho和Margaret J.Corasick 发明的</li></ul> <blockquote><ul><li>其实，Trie树跟AC自动机之间的关系，就像单模式串匹配中朴素的串匹配算法，跟KMP 算法之间的关系一样，只不过前者针对的是多模式串而已。所以，AC自动机实际上就是在Trie树之上，加了类似KMP的next数组，只不过此处的next数组是构建在树上罢了。</li></ul></blockquote> <h3 id="_7-1-bf算法『暴力』"><a href="#_7-1-bf算法『暴力』" class="header-anchor">#</a> 7.1.BF算法『暴力』</h3> <p>一顿暴力，直接贴代码</p> <p>//指针做输入，const修饰避免改动。</p> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">int</span> <span class="token function">BF</span><span class="token punctuation">(</span><span class="token keyword">const</span> <span class="token keyword">char</span> <span class="token operator">*</span>text <span class="token comment">/*in*/</span> <span class="token punctuation">,</span> <span class="token keyword">const</span> <span class="token keyword">char</span> <span class="token operator">*</span>pattern <span class="token comment">/*in*/</span> <span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token constant">NULL</span><span class="token operator">==</span>text<span class="token punctuation">)</span><span class="token operator">||</span><span class="token punctuation">(</span><span class="token constant">NULL</span><span class="token operator">==</span>pattern<span class="token punctuation">)</span><span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
		<span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">;</span><span class="token comment">//非法输入</span>
	<span class="token punctuation">}</span>
    
    <span class="token keyword">int</span> pos<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span><span class="token comment">//位置 </span>
    <span class="token keyword">while</span><span class="token punctuation">(</span><span class="token string">'\0'</span><span class="token operator">!=</span>text<span class="token punctuation">[</span>pos<span class="token punctuation">]</span><span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
    	<span class="token keyword">int</span> i<span class="token operator">=</span>pos<span class="token punctuation">;</span>	<span class="token comment">//text回溯 </span>
    	<span class="token keyword">int</span> j<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>	<span class="token comment">//pattern回溯 </span>
    	<span class="token keyword">int</span> sum<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>	<span class="token comment">//已经匹配字符长度</span>
    	<span class="token keyword">while</span><span class="token punctuation">(</span><span class="token string">'\0'</span><span class="token operator">!=</span>pattern<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
        	<span class="token keyword">if</span><span class="token punctuation">(</span>text<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">==</span>pattern<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
            	<span class="token operator">++</span>sum<span class="token punctuation">;</span>
            	<span class="token operator">++</span>j<span class="token punctuation">;</span>
            	<span class="token operator">++</span>i<span class="token punctuation">;</span> 
            <span class="token punctuation">}</span>
            <span class="token keyword">else</span>
            <span class="token punctuation">{</span>
            	<span class="token keyword">break</span><span class="token punctuation">;</span>
			<span class="token punctuation">}</span>
		<span class="token punctuation">}</span>
	 
        <span class="token keyword">if</span><span class="token punctuation">(</span>sum<span class="token operator">==</span><span class="token function">strlen</span><span class="token punctuation">(</span>pattern<span class="token punctuation">)</span><span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
        	<span class="token keyword">return</span> pos<span class="token punctuation">;</span>
		<span class="token punctuation">}</span>
        
        <span class="token operator">++</span>pos<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    
    <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span><span class="token comment">//匹配失败    </span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br></div></div><p>分析BF算法：</p> <blockquote><ul><li>时间复杂度$O(n*m)$</li> <li>空间复杂度$O(1)$</li></ul></blockquote> <p>其他补充：</p> <blockquote><ul><li>尽管理论上，BF算法的时间复杂度很高，但在实际的开发中，它却是一个比较常用的字符串匹配算法：</li></ul> <blockquote><ul><li>1.实际的软件开发中，大部分情况下，模式串和主串的长度都不会太长。而且每次模式串与主串中的子串匹配的时候，当中途遇到不能匹配的字符的时候，就可以就停止了，不需要把m个字符都比对一下。所以，尽管理论上的最坏情况时间复杂度大，但是，统计意义上，大部分情况下，算法执行效率要比这个高很多。</li> <li>2.BF算法思想简单，代码实现也非常简单。简单意味着不容易出错，如果有bug 也容易暴露和修复。<b>在工程中，在满足性能要求的前提下，简单是首选。</b>这也是我们常说的<b>KISS（Keep it Simple and Stupid）设计原则</b>。所以，在实际的软件开发中，绝大部分情况下，BF算法就够用了</li></ul></blockquote></blockquote> <h3 id="_7-2-rk算法"><a href="#_7-2-rk算法" class="header-anchor">#</a> 7.2.RK算法</h3> <p><b>联系</b>：RK算法是BF算法的改进，它巧妙借助了我们前面讲过的哈希算法，引入<font face="楷体" color="red" size="5">哈希算法</font>，时间复杂度立刻就会降低。
<b>难点</b>：设计一个可以应对各种类型字符的哈希算法并不简单</p> <p><b>思路</b>:我们通过哈希算法对主串中的n-m+1个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了（当然我们需要考虑哈希冲突的问题）。比较哈希值是非常快速的，所以效率提高了。
不过这又<b>引入一个问题</b>：通过哈希算法计算子串的哈希值的时候，我们需要遍历子串中的每个字符。尽管模式串与子串比较的效率提高了，但是，算法整体的效率并没有提高。有没有方法可以提高哈希算法计算子串哈希值的效率？
<b>哈希算法设计技巧</b>：我们假设要匹配的字符串的字符集中只包含K个字符，我们可以用一个K进制数来表示一个子串，这个K进制数转化成十进制数，作为子串的哈希值。</p> <p><b>没有冲突的哈希</b>：我们只需要比较一下模式串和子串的哈希值
<b>有冲突的哈希</b>：当存在哈希冲突的时候，有可能存在这样的情况，子串和模式串的哈希值虽然是相同的，但是两者本身并不匹配。解决方法很简单。当我们发现一个子串的哈希值跟模式串的哈希值相等的时候，我们只
需要再对比一下子串和模式串本身就好了。
当然，如果子串的哈希值与模式串的哈希值不相等，那对应的子串和模式串肯定也是不匹配的，就不需要比对子串和模式串本身了。</p> <p>总结：哈希算法的冲突概率要相对控制得低一些，如果存在大量冲突，就会导致 RK 算法的时间
复杂度退化，效率下降。极端情况下，如果存在大量的冲突，每次都要再对比子串和模式串本
身，那时间复杂度就会退化成$O(n*m)$</p> <p><b>但一般情况下，冲突不会很多，RK 算法的效率还是比 BF 算法高的。</b></p> <h3 id="_7-3-bm算法"><a href="#_7-3-bm算法" class="header-anchor">#</a> 7.3.BM算法</h3> <p>BM算法的名字取自于它的两位发明者，计算机科学家Bob Boyer 和JStrother Moore</p> <p>前面的背景：</p> <blockquote><ul><li>BF算法缺陷：在整个执行过程中,某些轮的比较没有意义，但BF算法还是老老实实地让模式串一位一位挪动。</li> <li>RK算法：为了克服这个缺陷BF，干脆回避了字符的直接比较，改为比较两个字符串的哈希值。但这样做可能产生哈希冲突，性能并不稳定。</li> <li>BM算法：则是想，那么我们能否仍然采用字符比较的思路，并且尽量减少无谓的比较呢?BM算法，本质上其实就是在<b>寻找一种规律</b>。借助这种规律，在模式串与主串匹配的过程中，当模式串和主串某个字符串匹配的时候，能够<b>跳过一些肯定不会匹配的情况</b>，将模式串往后多滑动几位。</li></ul></blockquote> <p>为了减少无谓的比较，BM算法制定了两条规则：</p> <blockquote><ul><li><b>坏字符规则</b>（bad character rule）</li> <li><b>好后缀规则</b>（good suffix shift）</li></ul></blockquote> <h3 id="_1、坏字符规则"><a href="#_1、坏字符规则" class="header-anchor">#</a> 1、坏字符规则</h3> <p>注意：</p> <blockquote><ul><li>BF和RK算法，在匹配的过程中，是按模式串的下标从小到大的顺序，依次与主串中的字符进行匹配的。符合我们的思维习惯</li> <li><b>BM算法的匹配顺序是按照模式串下标从大到小的顺序，倒着匹配的。</b> <b>优点</b>：当检测到第一个坏字符之后，我们并不需要让模式串一位一位向后挪动和比较。因为只有模式串与坏字符T对齐的位置也是字符T的情况下，两者才有匹配的可能，坏字符的位置越靠右，下一轮模式串的挪动跨度就可能越长，节省的比较次数也就越多。这就是BM算法从右向左检测的好处。</li></ul></blockquote> <p>定义：我们从<b>模式串的</b>末尾往前<b>倒着匹配</b>，当我们发现某个字符没法匹配的时候。我们把这个没有匹配的字符叫作<font color="red">坏字符(主串中的字符)</font>。</p> <h3 id="_2、好后缀规则"><a href="#_2、好后缀规则" class="header-anchor">#</a> 2、好后缀规则</h3> <p>所谓某个字符串s的后缀子串，就是最后一个字符跟s对齐的子串，比如abc的后缀子串就包
括c, bc。所谓前缀子串，就是起始字符跟s对齐的子串，比如abc的前缀子串有a, ab。 我们
从好后缀的后缀子串中，找一个最长的并且能跟模式串的前缀子串匹配的，假设是{v}, 然后将模
式串滑动到如图所示的位置。</p> <p>我们可以在每一轮的字符比较之后,按照坏字符和好后缀规则分别计算相应的挪动距离，哪一种距离更长，我们就把模式串挪动对应的长度。这种处理方法还可以避免，根据坏字符规则，计算得到的往后滑动的位数，有可能是负数的情况。</p> <p>完整代码：</p> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;cstdio&gt;</span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;cstdlib&gt;</span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;cmath&gt;</span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;cstring&gt;</span></span>

<span class="token keyword">const</span> <span class="token keyword">int</span> maxn<span class="token operator">=</span><span class="token number">256</span><span class="token punctuation">;</span>
<span class="token keyword">char</span> text<span class="token punctuation">[</span><span class="token number">1000</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">char</span> pattern<span class="token punctuation">[</span><span class="token number">500</span><span class="token punctuation">]</span><span class="token punctuation">;</span>

<span class="token comment">//1————坏字符规则</span>
<span class="token comment">//bc为散列表,构建坏字符哈希表</span>
<span class="token comment">//另外可以这样定义函数，用一级指针做输入，另一级指针做输出</span>
<span class="token comment">//void generateBC( const char *pattern/*in*/, int m , char * bc /*out*/)</span>
<span class="token keyword">void</span> <span class="token function">generateBC</span><span class="token punctuation">(</span><span class="token keyword">const</span> <span class="token keyword">char</span> pattern<span class="token punctuation">[</span><span class="token punctuation">]</span> <span class="token punctuation">,</span> <span class="token keyword">int</span> m <span class="token punctuation">,</span> <span class="token keyword">char</span> bc<span class="token punctuation">[</span><span class="token punctuation">]</span> <span class="token punctuation">)</span> 
<span class="token punctuation">{</span>
	<span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> maxn<span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span> 
	<span class="token punctuation">{</span>
		bc<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span> <span class="token comment">// 初始化 bc</span>
	<span class="token punctuation">}</span>

	<span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> m<span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span> 
	<span class="token punctuation">{</span>
		<span class="token keyword">int</span> ascii <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">)</span>pattern<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token comment">// 计算 b[i] 的 ASCII 值</span>
		bc<span class="token punctuation">[</span>ascii<span class="token punctuation">]</span> <span class="token operator">=</span> i<span class="token punctuation">;</span>
	<span class="token punctuation">}</span>

<span class="token punctuation">}</span>


<span class="token comment">//2————好后缀规则</span>
<span class="token comment">//GS（Good Suffix好后缀）存后缀的数组  prefix前缀</span>
<span class="token comment">//void generateGS(char *pattern /*in*/ , int m , int *suffix /*out*/ , bool * prefix /*out*/)</span>
<span class="token keyword">void</span> <span class="token function">generateGS</span><span class="token punctuation">(</span><span class="token keyword">char</span> pattern<span class="token punctuation">[</span><span class="token punctuation">]</span> <span class="token punctuation">,</span> <span class="token keyword">int</span> m<span class="token punctuation">,</span> <span class="token keyword">int</span> suffix<span class="token punctuation">[</span><span class="token punctuation">]</span> <span class="token punctuation">,</span> <span class="token keyword">bool</span> prefix<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">)</span> 
<span class="token punctuation">{</span>
	<span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> m<span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span> 
	<span class="token punctuation">{</span>
		<span class="token comment">// 初始化</span>
		suffix<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
		prefix<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>

	<span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> m <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token operator">++</span>i <span class="token punctuation">)</span> 
	<span class="token punctuation">{</span> 
		<span class="token comment">// pattern[0, i]</span>
		<span class="token keyword">int</span> j <span class="token operator">=</span> i<span class="token punctuation">;</span>
		<span class="token keyword">int</span> k <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token comment">// 公共后缀子串长度</span>
		<span class="token keyword">while</span> <span class="token punctuation">(</span>j <span class="token operator">&gt;=</span> <span class="token number">0</span> <span class="token operator">&amp;&amp;</span> pattern<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">==</span> pattern<span class="token punctuation">[</span>m<span class="token operator">-</span><span class="token number">1</span><span class="token operator">-</span>k<span class="token punctuation">]</span><span class="token punctuation">)</span> 
		<span class="token punctuation">{</span> 
			<span class="token comment">// 与 pattern[0, m-1] 求公共后缀子串</span>
			<span class="token operator">--</span>j<span class="token punctuation">;</span>
			<span class="token operator">++</span>k<span class="token punctuation">;</span>
			suffix<span class="token punctuation">[</span>k<span class="token punctuation">]</span> <span class="token operator">=</span> j<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span> 
			<span class="token comment">//j+1 表示公共后缀子串在 text[0, i] 中的起始下标</span>
		<span class="token punctuation">}</span>
		<span class="token keyword">if</span> <span class="token punctuation">(</span>j <span class="token operator">==</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span> 
			prefix<span class="token punctuation">[</span>k<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token boolean">true</span><span class="token punctuation">;</span> 
		<span class="token comment">// 如果公共后缀子串也是模式串的前缀子串</span>
	<span class="token punctuation">}</span>

<span class="token punctuation">}</span>



<span class="token comment">// j表示坏字符对应的模式串中的字符下标; m 表示模式串长度</span>
<span class="token keyword">int</span> <span class="token function">moveByGS</span><span class="token punctuation">(</span><span class="token keyword">int</span> j<span class="token punctuation">,</span> <span class="token keyword">int</span> m<span class="token punctuation">,</span> <span class="token keyword">int</span> suffix<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">bool</span> prefix<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">)</span> 
<span class="token punctuation">{</span>
	<span class="token keyword">int</span> k <span class="token operator">=</span> m <span class="token operator">-</span> <span class="token number">1</span> <span class="token operator">-</span> j<span class="token punctuation">;</span> 

	<span class="token comment">// 好后缀长度</span>
	<span class="token keyword">if</span> <span class="token punctuation">(</span>suffix<span class="token punctuation">[</span>k<span class="token punctuation">]</span> <span class="token operator">!=</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span> 
		<span class="token keyword">return</span> j <span class="token operator">-</span> suffix<span class="token punctuation">[</span>k<span class="token punctuation">]</span> <span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span>

	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> r <span class="token operator">=</span> j<span class="token operator">+</span><span class="token number">2</span><span class="token punctuation">;</span> r <span class="token operator">&lt;=</span> m<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span> <span class="token operator">++</span>r<span class="token punctuation">)</span> 
	<span class="token punctuation">{</span>
		<span class="token keyword">if</span> <span class="token punctuation">(</span>prefix<span class="token punctuation">[</span>m<span class="token operator">-</span>r<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token boolean">true</span><span class="token punctuation">)</span> 
		<span class="token punctuation">{</span>
			<span class="token keyword">return</span> r<span class="token punctuation">;</span>
		<span class="token punctuation">}</span>
	<span class="token punctuation">}</span>

	<span class="token keyword">return</span> m<span class="token punctuation">;</span>
<span class="token punctuation">}</span>



<span class="token comment">//n是text的长度，m是pattern的长度</span>
<span class="token keyword">int</span> <span class="token function">BM</span><span class="token punctuation">(</span><span class="token keyword">char</span> text<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">int</span> n<span class="token punctuation">,</span> <span class="token keyword">char</span> pattern<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">int</span> m <span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token keyword">if</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token constant">NULL</span><span class="token operator">==</span>text<span class="token punctuation">)</span><span class="token operator">||</span><span class="token punctuation">(</span><span class="token constant">NULL</span><span class="token operator">==</span>pattern<span class="token punctuation">)</span><span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">;</span>	<span class="token comment">//非法输入</span>
	<span class="token punctuation">}</span>

	<span class="token comment">//记录模式串中每个字符最后出现的位置</span>
	<span class="token keyword">char</span> bc<span class="token punctuation">[</span>maxn<span class="token punctuation">]</span><span class="token punctuation">;</span><span class="token comment">//bad char 坏字符简写</span>
	<span class="token function">generateBC</span><span class="token punctuation">(</span> pattern <span class="token punctuation">,</span> m<span class="token punctuation">,</span> bc<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">//构建坏字符哈希表</span>


	<span class="token keyword">int</span> <span class="token operator">*</span> suffix<span class="token operator">=</span><span class="token punctuation">(</span><span class="token keyword">int</span> <span class="token operator">*</span><span class="token punctuation">)</span><span class="token function">malloc</span><span class="token punctuation">(</span> <span class="token keyword">sizeof</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">)</span> <span class="token operator">*</span> m<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">bool</span> <span class="token operator">*</span> prefix<span class="token operator">=</span><span class="token punctuation">(</span><span class="token keyword">bool</span> <span class="token operator">*</span><span class="token punctuation">)</span><span class="token function">malloc</span><span class="token punctuation">(</span> <span class="token keyword">sizeof</span><span class="token punctuation">(</span><span class="token keyword">bool</span><span class="token punctuation">)</span> <span class="token operator">*</span> m<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token comment">//好后缀数组</span>
	<span class="token function">generateGS</span><span class="token punctuation">(</span>pattern<span class="token punctuation">,</span> m<span class="token punctuation">,</span> suffix<span class="token punctuation">,</span> prefix<span class="token punctuation">)</span><span class="token punctuation">;</span>

	<span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> 
	<span class="token comment">// j 表示主串与模式串匹配的第一个字符</span>
	<span class="token keyword">while</span> <span class="token punctuation">(</span>i <span class="token operator">&lt;=</span> n <span class="token operator">-</span> m<span class="token punctuation">)</span> 
	<span class="token punctuation">{</span>
		<span class="token keyword">int</span> j<span class="token punctuation">;</span>
		<span class="token keyword">for</span> <span class="token punctuation">(</span>j <span class="token operator">=</span> m <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span> j <span class="token operator">&gt;=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token operator">--</span>j<span class="token punctuation">)</span> 
		<span class="token punctuation">{</span> 
			<span class="token comment">// 模式串从后往前匹配</span>
			<span class="token keyword">if</span> <span class="token punctuation">(</span>text<span class="token punctuation">[</span>i<span class="token operator">+</span>j<span class="token punctuation">]</span> <span class="token operator">!=</span> pattern<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token keyword">break</span><span class="token punctuation">;</span> 
			<span class="token comment">// 坏字符对应模式串中的下标是 j</span>
		<span class="token punctuation">}</span>
		<span class="token keyword">if</span> <span class="token punctuation">(</span>j <span class="token operator">&lt;</span> <span class="token number">0</span><span class="token punctuation">)</span> 
		<span class="token punctuation">{</span>
			<span class="token comment">//释放堆中内存，防止内存泄漏</span>
			<span class="token function">free</span><span class="token punctuation">(</span>suffix<span class="token punctuation">)</span><span class="token punctuation">;</span>
			<span class="token function">free</span><span class="token punctuation">(</span>prefix<span class="token punctuation">)</span><span class="token punctuation">;</span>

			<span class="token comment">// 匹配成功，返回主串与模式串第一个匹配的字符的位置</span>
			<span class="token keyword">return</span> i<span class="token punctuation">;</span> 
		<span class="token punctuation">}</span>
		<span class="token keyword">int</span> x <span class="token operator">=</span> j <span class="token operator">-</span> bc<span class="token punctuation">[</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">)</span>text<span class="token punctuation">[</span>i<span class="token operator">+</span>j<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
		<span class="token keyword">int</span> y <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
		<span class="token keyword">if</span> <span class="token punctuation">(</span>j <span class="token operator">&lt;</span> m<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span> 
		<span class="token punctuation">{</span> 
			<span class="token comment">//如果有好后缀的话</span>
			y <span class="token operator">=</span> <span class="token function">moveByGS</span><span class="token punctuation">(</span>j<span class="token punctuation">,</span> m<span class="token punctuation">,</span> suffix<span class="token punctuation">,</span> prefix<span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token punctuation">}</span>

		<span class="token comment">//选择坏字符和好后缀中能让它后移更远的</span>
		<span class="token keyword">int</span> max_num<span class="token operator">=</span>y<span class="token punctuation">;</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span>x<span class="token operator">&gt;</span>y<span class="token punctuation">)</span>
		<span class="token punctuation">{</span>
			max_num<span class="token operator">=</span>x<span class="token punctuation">;</span>
		<span class="token punctuation">}</span>
		i <span class="token operator">=</span> i <span class="token operator">+</span> max_num<span class="token punctuation">;</span>

	<span class="token punctuation">}</span>

	<span class="token comment">//释放堆中内存，防止内存泄漏</span>
	<span class="token function">free</span><span class="token punctuation">(</span>suffix<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token function">free</span><span class="token punctuation">(</span>prefix<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span><span class="token comment">//未匹配到</span>
<span class="token punctuation">}</span>


<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">&quot;%s%s&quot;</span><span class="token punctuation">,</span>text<span class="token punctuation">,</span>pattern<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">int</span> n<span class="token operator">=</span><span class="token function">strlen</span><span class="token punctuation">(</span>text<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">int</span> m<span class="token operator">=</span><span class="token function">strlen</span><span class="token punctuation">(</span>pattern<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">&quot;%d\n&quot;</span><span class="token punctuation">,</span><span class="token function">BM</span><span class="token punctuation">(</span>text<span class="token punctuation">,</span>n<span class="token punctuation">,</span>pattern<span class="token punctuation">,</span>m<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

	<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span> 
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br><span class="line-number">61</span><br><span class="line-number">62</span><br><span class="line-number">63</span><br><span class="line-number">64</span><br><span class="line-number">65</span><br><span class="line-number">66</span><br><span class="line-number">67</span><br><span class="line-number">68</span><br><span class="line-number">69</span><br><span class="line-number">70</span><br><span class="line-number">71</span><br><span class="line-number">72</span><br><span class="line-number">73</span><br><span class="line-number">74</span><br><span class="line-number">75</span><br><span class="line-number">76</span><br><span class="line-number">77</span><br><span class="line-number">78</span><br><span class="line-number">79</span><br><span class="line-number">80</span><br><span class="line-number">81</span><br><span class="line-number">82</span><br><span class="line-number">83</span><br><span class="line-number">84</span><br><span class="line-number">85</span><br><span class="line-number">86</span><br><span class="line-number">87</span><br><span class="line-number">88</span><br><span class="line-number">89</span><br><span class="line-number">90</span><br><span class="line-number">91</span><br><span class="line-number">92</span><br><span class="line-number">93</span><br><span class="line-number">94</span><br><span class="line-number">95</span><br><span class="line-number">96</span><br><span class="line-number">97</span><br><span class="line-number">98</span><br><span class="line-number">99</span><br><span class="line-number">100</span><br><span class="line-number">101</span><br><span class="line-number">102</span><br><span class="line-number">103</span><br><span class="line-number">104</span><br><span class="line-number">105</span><br><span class="line-number">106</span><br><span class="line-number">107</span><br><span class="line-number">108</span><br><span class="line-number">109</span><br><span class="line-number">110</span><br><span class="line-number">111</span><br><span class="line-number">112</span><br><span class="line-number">113</span><br><span class="line-number">114</span><br><span class="line-number">115</span><br><span class="line-number">116</span><br><span class="line-number">117</span><br><span class="line-number">118</span><br><span class="line-number">119</span><br><span class="line-number">120</span><br><span class="line-number">121</span><br><span class="line-number">122</span><br><span class="line-number">123</span><br><span class="line-number">124</span><br><span class="line-number">125</span><br><span class="line-number">126</span><br><span class="line-number">127</span><br><span class="line-number">128</span><br><span class="line-number">129</span><br><span class="line-number">130</span><br><span class="line-number">131</span><br><span class="line-number">132</span><br><span class="line-number">133</span><br><span class="line-number">134</span><br><span class="line-number">135</span><br><span class="line-number">136</span><br><span class="line-number">137</span><br><span class="line-number">138</span><br><span class="line-number">139</span><br><span class="line-number">140</span><br><span class="line-number">141</span><br><span class="line-number">142</span><br><span class="line-number">143</span><br><span class="line-number">144</span><br><span class="line-number">145</span><br><span class="line-number">146</span><br><span class="line-number">147</span><br><span class="line-number">148</span><br><span class="line-number">149</span><br><span class="line-number">150</span><br><span class="line-number">151</span><br><span class="line-number">152</span><br><span class="line-number">153</span><br><span class="line-number">154</span><br><span class="line-number">155</span><br><span class="line-number">156</span><br><span class="line-number">157</span><br></div></div><h2 id="参考资料"><a href="#参考资料" class="header-anchor">#</a> 参考资料</h2> <ul><li>[日]秋叶拓哉 / [日]岩田阳一 / [日]北川宜稔，《<a href="https://book.douban.com/subject/24749842/" target="_blank" rel="noopener noreferrer">挑战程序设计竞赛<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a>》</li> <li>labuladong的算法小抄</li> <li>GitHub，机试技巧与STL</li> <li>柳婼，《从放弃C语⾔到使⽤C++刷算法的简明教程》</li></ul></div> <div class="page-edit"><!----> <!----></div> <!----> </div> <!----></div></div>
    <script src="/assets/js/app.c70e21ad.js" defer></script><script src="/assets/js/55.d8f9004b.js" defer></script>
  </body>
</html>
